[python] 1463. 1로 만들기

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

 

 

풀이 

 

dp는 점화식을 찾는 것이 문제 풀이의 핵심입니다. 

-1, /2, /3의 방법으로 점화식을 찾으려고 노력했는데요.

 

예를 들어, 그림과 같이 6을 구하는 횟수를 구할 때,

1만큼 작은 5보다는 1회 증가하고 (+1하면 되니까)

2로 나눈 3보다도 1회 (*3 하면 되니까),

3으로 나눈 2보다도 1회(*2 하면 되니까) 증가합니다.

 

이렇게 점화식을 찾았으며, 코드로 구현하면 다음과 같습니다.

 

 

 

x = int(input())
dp = [0] * (x+1) # 계산된 결과를 저장하기 위한 DP 테이블 초기화

for i in range(2, x+1): # 보텀업
    dp[i] = dp[i-1] + 1 # 현재의 수에서 1을 빼는 경우

    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)

print(dp[x])