알고리즘 - Python / 백준 - 1463번 : 1로 만들기

1463번: 1로 만들기 (acmicpc.net)

1463번: 1로 만들기

 

---

풀이

• DP 문제 이므로 점화식을 찾는다.
• 3가지 연산에 대해서 점화식을 세우고 각 점화식의 결과 중 최소값을 택하여 DP 배열에 넣는다.
• 전체 DP 배열을 모두 구한후 해당하는 DP[N]을 출력한다.

 

import sys

n = int(sys.stdin.readline())

dp = [0,0,1,1]
for i in range(4,1000001):
  dp.append(0)
  dp33 = 1000000
  dp22 = 1000000
  if i % 3 == 0:
    dp33 = dp[int(i/3)]
  if i % 2 == 0:
    dp22 = dp[int(i/2)]
  dp[i] = min( dp[i-1]+1, dp22+1 , dp33+1)

print(dp[n])

 

---