[BOJ] 1463번 - 1로 만들기 (feat. python main함수)

수많은 실패를 거듭하고 처음으로 DP문제 해결!

이 문제는 내가 한 번도 안 풀어본 DP문제였다. DP문제를 어떻게 접근하고 해결하는지를 알지 못해 DP알고리즘부터 찾아보며 대략적으로 문제에 어떻게 접근해야 하는지를 알아본 후 바로 문제 해결하러 고고!

---

문제 후기

처음에는 하향식(Top Down)방식으로 문제를 해결하려 했다. 문제는 재귀 제한이 걸려버린 것. 그래서 3번 런타임 에러로 실패. system 라이브러리를 이용해서 재귀 제한을 늘려도 해결이 되지 않아 상향식으로 풀기로 했다. 상향식으로 해결하니 값을 미리미리 저장해서 해결하기 때문에 재귀를 사용할 일이 없고, 최솟값 비교만 잘해주면 해결! 이번 문제를 통해서 Python의 main함수를 작성하는 방법도 알게되었다. 정답 코드를 작성하면서 설명하겠다.

 

문제 풀이

import sys

def makeOne(n):
    for i in range(2, n+1):
        memo[i] = memo[i-1]
        if i % 3 == 0:
            memo[i] = min(memo[i], memo[i//3])
        if i % 2 == 0:
            memo[i] = min(memo[i], memo[i//2])
        memo[i] += 1
    return memo[n]

# 재귀로 해결한 코드 : 재귀재한 걸려서 실패
# def makeOne(n):
#     if memo[n] > 0:
#         return memo[n]
#
#     if n == 1:
#         return memo[n]
#
#     memo[n] = makeOne(n-1)
#     if n % 3 == 0:
#         memo[n] = min(memo[n], makeOne(n // 3))
#     if n % 2 == 0:
#         memo[n] = min(memo[n], makeOne(n // 2))
#
#     memo[n] += 1
#     return memo[n]

# Python main 함수이다.
if __name__ == "__main__":
    n = int(sys.stdin.readline())
    memo = [0] * (n + 1)
    print(makeOne(n))

상향식

1. 일단 계산된 문제의 값을 저장할 공간이 필요하니 "0"이 저장된 리스트를 만든다. 길이는 n+1(인덱스를 실제 숫자처럼 사용하기 위해).
2. 1은 계산 할 필요 없이 값이 "0"이므로 2부터 n까지 반복문을 돌려서 각 리스트의 value에 "-1"한 값, "//3"한 값, "//2"한 값을 비교해 가장 작은 값을 memo에 추가하고 마지막에 "+1"을 해준다.
3. 가장 마지막에 memo[n]를 return

 

하향식

1. 위와 동일
2. memo[n]이 값이 있으면 그 값을 return
3. n이 1이면 memo의 값이 0이니까 전달
4. memo [n]의 값을 memo [n-1]의 값으로 설정(-1 했을 때 최솟값)
5. "//3", "//2" 한 값을 각각 비교해서 작은 값을 최종으로 대입 ("//3"을 먼저 한 이유는 //3을 했을 때 더 작은 값이 나올 가능성이 높기 때문)
6. 마지막으로 최솟값에 "+1"을 해준다
7. 마지막에는 memo[n]을 return

BOJ Solutions: https://github.com/Isaac-Lee/BOJ-Algorithm