백준 1463 1로 만들기

과정

• 정수 N 길이의 리스트를 만듦.
• 각 인덱스에 해당하는 값이 1이 될 때까지 몇 번의 연산을 거치는지를 저장.
• i를 6, 3, 2로 나누어 떨어지는 경우와 그렇지 않은 경우로 나눔.
  • 6으로 나누어 떨어지는 수는 i//2, i//3, i-1 의 위치에 있는 값 중 최소값에 +1
  • 3으로 나누어 떨어지는 수는 i//3, i-1 의 위치에 있는 값 중 최소값에 +1
  • 2으로 나누어 떨어지는 수는 i//2, i-1 의 위치에 있는 값 중 최소값에 +1
  • 그 외는 i-1 의 위치에 있는 값에 +1

N = int(input())
dp = [0] * (N+1)
for i in range(1, N+1):
    if i == 1:
        dp[1] = 0
    elif i == 2:
        dp[2] = 1
    elif i == 3:
        dp[3] = 1
    else:
        if i% 6 == 0:
            dp[i] = min(dp[i//2], dp[i//3], dp[i-1]) + 1
        elif i % 3 == 0:
            dp[i] = min(dp[i//3], dp[i-1]) + 1
        elif i % 2 == 0:
            dp[i] = min(dp[i//2], dp[i-1]) +1
        else:
            dp[i] = dp[i-1] + 1
print(dp[N])