[백준] 1463 1로 만들기 (파이썬/python) dp, bfs

🎈문제

https://www.acmicpc.net/problem/1463

 

🎁어떤 알고리즘?

1. bfs, dp

2. 사실 가장 먼저 생각난 것은 bfs이다. 1차원 리스트에서 “최소 몇번 ~를 해야하는지 구하시오”와 같은 문제가 나왔을 경우 bfs를 떠올릴 수 있도록 공부했기 때문이다.

3. 하지만 이 문제의 경우 dp를 이용하면 더 빠르게 동작한다.

bfs : 852ms

dp : 644ms

 

4. 밑에 dp와 bfs로 모두 풀어보고 자세한 설명을 첨부했다.

 

💻 dp 코드

# 1463 1로 만들기 (dp 사용)

# 1. 입력 받기
n = int(input())
dp = [0 for _ in range(n+1)]

for i in range(2,n+1):
    dp[i] = dp[i-1] + 1
    '''
    우리는 1부터 n을 찾아가는 방식을 이용할 건데,
    4를 예로 들면, 4가 되려면 1씩 더해서  
    1->2->3->4의 과정을 통해서 각각 다음과 같은 연산 횟수가 필요하다는 것을 알 수 있다.
    0  1  2  3
    그런데 4는 2로 나누어 떨어지므로 2에서 4로 바로 올 수 있다. -> min(3,2)를 통해 2가 됨
    또한 4는 3에서 1을 더함으로써 2번만에 올 수 있다. -> min(2,2)를 통해 2로 최종 결정 됨
    1->2->3->4
    0  1  1  2
    이렇게 최악의 연산 횟수(3)과 더 적은 연산횟수(2)를 min()함수를 통해
    비교한 후, 더 적은 연산횟수를 채택해 줌으로써 최솟값을 얻을 수 있다.
    '''
    if i%2 == 0:  # 2로 나누어 떨어지면
        dp[i] = min(dp[i],dp[i//2]+1)
    if i%3 == 0:    # 3으로 나누어 떨어지면
        dp[i] = min(dp[i],dp[i//3]+1)

print(dp)
print(dp[n])

🎄코드 설명

    우리는 1부터 n을 찾아가는 방식을 이용할 건데,

    4를 예로 들면, 4가 되려면 1씩 더해서  

    1->2->3->4의 과정을 통해서 각각 다음과 같은 연산 횟수가 필요하다는 것을 알 수 있다.

    0  1  2  3

    그런데 4는 2로 나누어 떨어지므로 2에서 4로 바로 올 수 있다.

    1->2->3->4

    0  1  2  2 가 되는 것이다.

    이렇게 최악의 연산 횟수(3)과 더 적은 연산횟수(2)를 min()함수를 통해

    비교한 후, 더 적은 연산횟수를 채택해 줌으로써 최솟값을 얻을 수 있다.

 

💻 bfs 코드

from collections import deque

def bfs(x):
    deq = deque()
    deq.append(x)

    while deq:
        x = deq.popleft()

        if x == n:
            print(graph[x])
            return

        for i in [2*x,3*x,x+1]:
            if i > n:
                continue
            if graph[i] == 0:
                graph[i] = graph[x]+1
                deq.append(i)
    return

# 1. 입력 받기
n = int(input())

graph = [0 for _ in range(n+1)]

# 3. 탐색
bfs(1)
print(graph)

🎄코드 설명

1부터 시작해서 [2*x, 3*x, x+1] 세 방법을 돌아가면서 수행하는데, 각 자리에 최솟값이 먼저 들어가게 되므로

한번도 거치지 않은 빈 공간인지만을 판단해 주면 된다.

1->2->3->4->5->6

0    1    1    2     3    2