1463. 1로 만들기

어렵다.

동적 프로그래밍은 점화식을 세우면 풀 수 있다고 했는데,

점화식은 세웠는데 그걸로 어떻게 구현해야할지 재귀에서 한참 헤맸다.

처음이라 그런지, 피보나치만 생각하고 Top-down만 생각했던 게 실수였던 것 같다.

또, 점화식이 D(n) = min(D(n/3), D(n/2), D(n-1)) + 1 이런 식으로 나오다보니 자연스럽게 탑다운만 생각했다.

 

사실, 탑다운도 가능하고 바텀업도 가능하다.

하지만 실행 시 탑다운 방식은 큰 수를 넣으면 재귀가 너무 깊다고 하면서 오류가 뜬다.

 

 

 

Top-Down (큰 수 오류)

enter = int(input())
m = [-1 for i in range(enter + 1)]  # memoization

def dp(n):
    if n == 1:
        return 0
    if n == 2 or n == 3:
        return 1
    if m[n] != -1:
        return m[n]
    temp1 = dp(n-1) + 1  # -1 했을 때 최소 연산
    temp2 = temp1  # 0으로 하면 안되서 temp1과 같게 해 줌
    temp3 = temp1
    if n % 2 == 0:
        temp2 = dp(n//2) + 1
    if n % 3 == 0:ㅁ
        temp3 = dp(n//3) + 1
    m[n] = min([temp1, temp2, temp3])
    return m[n]

print(dp(enter))

 

 

 

Bottom-Up

n = int(input())
m = []  # 미리 초기화를 하면 밑부분 m[0]~m[3]을 초기화해주는 부분에서 out of index 날 수 있다

m.append(0)
m.append(0)
m.append(1)
m.append(1)

for i in range(4, n+1):
    m.append(m[i-1] + 1);
    if(i % 2 == 0):
        m[i] = min(m[i], m[i//2] + 1) 
    if(i % 3 == 0):
        m[i] = min(m[i], m[i//3] + 1) 

print(m[n])

 

이 문제에서 생각해내지 못한 것은 10번째 줄이다.

-1 하는 것을 기본으로 놓고,

그 이후에 2나 3으로도 계산해보면서 무엇이 최솟값인지 비교해보는 방식으로 푸는 것이었다.