[알고리즘][Python] 백준(BOJ) 1463 1로 만들기_파이썬

DP

1463 1로 만들기    https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

 

 

 

문제 풀기 전 공부할 것 : Dynamin Programming(동적 프로그래밍)

 

 

 

 

 

 

 

풀이 1

점화식

정수 X로 1을 만드는 연산 횟수

1. dp[x-1] + 1 : x-1로 1을 만드는 연산에 1을 더한 값
2. dp[x//2] + 1 : x/2로 1을 만드는 연산에 1을 더한 값
3. dp[x//3] + 1 : x/3로 1을 만드는 연산에 1을 더한 값 

위의 3가지 경우의 값 중 가장 작은 값이 정수 X로 1을 만드는 연산 횟수의 최솟값이다.

 

 

n = int(input())

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

for i in range(1, n+1):
    if i == 1:
        dp[i] == 0
    else:
        dp[i] = dp[i-1] + 1
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i//3]+1)
        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i//2]+1)
            
print(dp[n])

 

 

 

 

 

풀이 2

 

from collections import deque

x = int(input())
dp = [0 for _ in range(x+1)]
dp[x] = 0
que = deque([x])
while que:
    num = que.popleft()
    if num % 3 == 0 and dp[num//3] == 0:
        dp[num//3] = dp[num] + 1
        que.append(num//3)
    if num % 2 == 0 and dp[num//2] == 0:
        dp[num//2] = dp[num] + 1
        que.append(num//2)
    if num-1 >= 1 and dp[num-1] == 0:
        dp[num-1] = dp[num] + 1
        que.append(num-1)

 

 

 

 

 

복습

점화식