BAEKJOON 1463 : 1로 만들기

# <BAEKJOON 1463: 1로 만들기>

# dp[N] 은 N이 1이 되는 동안 연산 횟수의 최솟값을 의미한다.
# ex) dp[1]=0, dp[2]=1, dp[3]=1 ...
# 따라서 거슬러 올라가면서 dp[N]을 기록하는 것이 이 문제의 풀이 방법이다.

X = int(input())

# 배열 생성.
# 0번째 인덱스는 사용하지 않을 것이므로 X+1 만큼의 크기로 생성.
dp = [0] * (X+1)

for i in range(2, X+1):

    # 일단, <1을 빼는 경우의 연산 횟수>를 저장한다.
    dp[i] = dp[i-1] + 1

    if(i%3==0):

        # 3의 배수일 때,
        # <1을 빼는 경우의 연산 횟수> 와 <3으로 나누는 경우의 연산 횟수> 중 더 낮은 것을 선택한다.
        dp[i] = min(dp[i//3]+1, dp[i])

    if(i%2==0):

        # 2의 배수일 때,
        # <2로 나누는 경우의 연산 횟수>와 <위에서 구한 연산 횟수> 중 더 낮은 것을 선택한다.
        dp[i] = min(dp[i//2]+1, dp[i])

    # 최종적으로 dp[i] 에는 최소한의 연산 횟수가 저장된다.
    # i가 거슬러 올라가면서, 저장했던 것들을 이용하면서 반복한다. (DP bottom-up)

# 마침내 dp[X]를 구하게 된다.
print(dp[X])

첫 DP 문제이다. DP의 개념을 모르는 상태로 접했다.

그래서 3의 배수 => 2의 배수 => 1 빼기 순으로 우선순위에 중점을 두고 알고리즘을 세웠다.
그렇게는 안되더라.
경우의 수가 많은데 이 최적의 경우의 수를 if로 해결해보려고 끙끙댔다.

어쩔 수 없이 블로그를 보고 거의 따라친다음 주석을 달며 이해했다.

DP 란 문제를 작은 문제로 쪼개고 그 결과를 기록해서 => 기록된 값들로 마침내 큰 문제를 푸는 기법이다.

bottom-up(for문 이용), top-down(재귀함수 이용) 두 가지 방향이 있다.