[DP]1463번 1로만들기

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 20분

1. 문제 설명

- https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

2. 접근 방식

- i가 6의 배수일 때,  3의 배수일 때,  2의 배수일 때를 나눠서 생각한다. 해당 위치에서, 어떻게 감소시키는게 더 효율적일지  생각한다.

- Botton-up으로 dp를 쌓는다.

3. 코드

n =int(input())

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

4. 코멘트

- 순서가 중요하다고 할 수 있어 보인다. 예를 들어 12일 때, 6이 2보다 먼저 사용되어야 한다.