백준 1463 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

풀이

• 그리디 알고리즘 문제가 아니다
  10의 경우 10 - 9 - 3 - 1 로 3번 만에 만든다
  그리디 알고리즘 문제라면 10 - 5 - 4 - 2 - 1 로 4번 시도해야한다
  그리디 알고리즘으로 풀 경우의 해가 유효성이 검증되지 못했다.

• 메모제이션 기법을 사용한다
  10 - 9 - 3 - 1로 10의 해를 구한다.
  이 때 3은 (1을 구하는 횟수 + 1), 9는 (3을 구하는 횟수 + 1)이 성립한다
  주어질 숫자의 최소 횟수를 아래서부터 계속 만들어가면, 최솟 값을 구할 수 있다.

코드

import sys

num = int(sys.stdin.readline())
dp = [0]*(num+1)

for i in range(2,num+1):
    dp[i]=dp[i-1]+1

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