[백준/Python] 1463번 - 1로 만들기

문제

1463번 - 1로 만들기

해결 과정

• DP로 풀기
• dp[5] 는 5를 1로 만드는 최소 연산 횟수

시행착오

• 다 계산해서 비교하는 방법으로 구현했는데 시간초과 ^^,,

import sys
x = int(sys.stdin.readline())
array = [x]
cnt = 0
while True:
  sub = []
  cnt += 1
  for i in range(len(array)):
    if array[i] % 3 == 0:
      sub.append(array[i] // 3)
    if array[i] % 2 == 0:
      sub.append(array[i] // 2)
    sub.append(array[i] - 1)
  array = sub
  if 1 in sub:
    break
print(cnt)

• 그리고 힌트를 봐버렸다. 하지만 점화식을 어떻게 세우지?
  
  • 1에서 x까지 가는 점화식을 세워야겠다. 작은 문제에서 큰 문제로 풀어가는 방식!

풀이

import sys
x = int(sys.stdin.readline())

dp = [0] * (x+1)

for i in range(2,x+1):
  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[x])

• 우선 for i in range(2,x+1): 에서 2부터 시작한 이유는 dp[1] 은 이미 1이므로 연산이 필요하지 않기 때문에 dp[1] = 0 이다.
• 1을 빼고, 3을 나눠보고, 2를 나눠보는 세가지 방법을 다 진행한 후 가장 작은 값을 넣는것.

https://seongonion.tistory.com/40
https://jae04099.tistory.com/199