실버3 1로 만들기(1463)

1463번: 1로 만들기

DP문제를 잘 몰라서 처음에는 8까지 모든 경우의 수를 적었다. 적고 보니 어떻게 풀어야할 지 보여서 쉽게 풀 수 있다. 3이나 2로 나눠지면 best를 업데이트를 했다. 최소값만 넣을 수 있게 min을 활용해서 풀고, 마지막에 append하기 전에 min값을 넣었다. 이렇게 풀고 성공(832ms)은 했는데 생각을 해보니 굳이 인덱스를 넣을 필요가 없다는 것을 알게 되었다.

import sys
input = sys.stdin.readline

num = int(input())
memo = [(0,0), (1,0)]
for i in range(2, num+1):
  best = 99999999
  if i % 3 == 0:
    best = memo[i//3][1]+1
  if i % 2 == 0:
    best = min(memo[i//2][1]+1, best)
  memo.append((i, min(memo[i-1][1]+1, best)))

print(memo[num][1])

그래서 아래와 같이 다시 풀었더니 조금 더 줄어든 632ms로 나왔다. 그래서 좀 더 줄 일 수 없을까 했는데 또 고민해보니 best를 저렇게 초기화하지 않고, 처음부터 1을 뺀 값을 넣어서 min값을 업데이트를 하게 만들었다.

import sys
input = sys.stdin.readline

num = int(input())
memo = [0, 0]
for i in range(2, num+1):
  best = 99999999
  if i % 3 == 0:
    best = memo[i//3]+1
  if i % 2 == 0:
    best = min(memo[i//2]+1, best)
  memo.append(min(memo[i-1]+1, best))

print(memo[-1])

아래와 같이 구현해서 580ms로 줄일 수 있었다.

import sys
input = sys.stdin.readline

num = int(input())
memo = [0, 0]
for i in range(2, num+1):
  best = memo[i-1]+1
  if i % 2 == 0:
    best = min(memo[i//2]+1, best)
  if i % 3 == 0:
    best = min(memo[i//3]+1, best)
  memo.append(best)

print(memo[-1])