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

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

---

문제

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

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

---

입력 & 출력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

---

코드

input = __import__('sys').stdin.readline
n = int(input().rstrip())

list_n = [0] * (n + 1)

list_n[0] = 0
list_n[1] = 0

for i in range(2, n + 1) :
    list_n[i] = list_n[i - 1] + 1
    if i % 2 == 0 and list_n[i] -1 > list_n[int(i / 2)] :
        list_n[i] = list_n[int(i / 2)] + 1
    if i % 3 == 0 and list_n[i] - 1 > list_n[int(i / 3)] :
        list_n[i] = list_n[int(i / 3)] + 1

print(list_n[n])

 

풀이

DP를 이용하여 풀이를 진행했다. DP가 아닌 단순 반복을 이용한 풀이도 처음엔 가능하다고 생각했지만 이 문제의 경우, 풀이 시간이 단순 반복으로는 해결하기 힘들도록 설정되어 있다. 
어떤 경우에 DP를 생각하고 어떻게 memorization을 구현해야 할 지, 아직은 내 역량이 부족해 추가적인 학습이 필요해 보인다. 😓