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

문제

1463번: 1로 만들기

입력

• 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

• 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

입력 예제

2

출력 예제

1

문제 풀이

• i번째 인덱스의 값은 i를 1로 만드는 데 걸리는 횟수 이므로
• 맨 처음 1을 빼서 i값을 만드는 값을 i번째 인덱스에 넣는다.
• 그 후, 만약 i가 2나 3의 배수라면, 나누기 연산을 한 값이 최소 연산 횟수 일 것이므로,  [i // 2], [i//3]번째 인덱스의 값에 1을 더해서 넣어준다.
• 따라서 점화식은 아래와 같다.

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

코드

n = int(input())
dp = [0] * 1000001

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