BOJ1463 - 1로 만들기

아래 링크의 가이드에 따라 문제를 풀고 있다.
알고리즘 가이드

---

문제
1463 - 1로 만들기

---

위 가이드의 DP 첫 번째 문제 1로 만들기.
허무한 구멍에서 헤매다가 질문을 검색해 해결했다.

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

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

입력
1보다 크거나 같고, $10^{6}$보다 작거나 같은 정수 N이 주어짐.

출력
주어진 N에서 주어진 규칙에 따라 1을 만들 때 최소한의 연산 수를 출력.

생각했던 해법

• 3으로 나누어지면 그게 제일 빠른 방법일테니깐,
• 우선 3으로 나눠지는지 확인해서 나눠지면 ans[i - 1]과 ans[i // 3]을 비교.
• 마찬가지로, 3으로 나눠지지 않고 2로 나눠진다면 ans[i - 1]과 ans[i // 2]을 비교.
• 2, 3 모두로 나눠지지 않는다면 ans[i] = ans[i - 1] + 1

실수

• 6으로 나눠질 경우, 2로 나눴을 때, 3으로 나눴을 때, 1로 뺐을 때 모두와 비교해야 함.
• 그런데 안 했다..

코드

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