[BOJ][python] 1로 만들기

dynamic과 재귀제한 -> 상향식 구현

 

 

문제

---

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

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

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

 

입력

---

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

 

나의 풀이

---

언뜻 보면 그냥 순차적으로 3으로 나눠지는지 2로 나눠지는지 확인하면서 구하면 될 것 같지만, 주어진 경우의 수가 생각보다 많이 나오는 것을 확인할 수 있습니다.

이런 문제의 경우 DP를 사용, 큰 문제를 작은 문제로 나누어 해결하는 방법이 필요합니다.

다음과 같이 재귀적인 방법으로 DP를 구현할 수 있습니다.

n = int(input())
d = [0 for _ in range(n+1)]
def get_proc(n):
    if n==1:
        return 0
    if d[n] > 0:
        return d[n]
    d[n] = get_proc(n-1) + 1
    if (n%3 == 0):
        temp = get_proc(n//3) + 1
        if(d[n] > temp):
            d[n] = temp
    if (n%2 == 0):
        temp = get_proc(n//2) + 1
        if(d[n] > temp):
            d[n] = temp
    return d[n]

print(get_proc(n))

정답을 구하는 것과 별개로 백준에서 실행하면 재귀횟수 제한 때문에 런타임 에러가 발생합니다.
메모리 크기를 줄이면서 런타임에러를 피하기 위해서는 다음과 같이 하향식이 아닌 상향식으로 DP를 구현해야 합니다.

n = int(input())

d = [0 for _ in range(n+1)]
d[1] = 0

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