백준 1463: 1로 만들기

✔ 풀이를 위한 아이디어

• 동적 프로그래밍 (Dynamic Programming)
  
  

✔ 수정 전 코드

import sys

def make_one(x, count):
    if x == 1:
        print(count)
        return
    if x == 2:
        x = x // 2
    elif x % 3 == 0:
        x = x // 3
    elif (x & (x-1)) == 0: #2의 n제곱 판별
        x = x // 2
    elif x % 3 == 1:
        x = x - 1
    elif x % 3 == 2 and x % 2 == 0:
        x = x // 2
    elif x % 3 == 2 and x % 2 == 1:
        x = x - 1
    count += 1
    make_one(x, count)


if __name__=="__main__":
    X = int(sys.stdin.readline())
    count = 0
    make_one(X, count)

• 처음에는 그리디 알고리즘(Greedy Algorithm)을 통해 구현할 수 있을 것이라고 생각했다. 그래서 다양한 케이스들을 직접 테스트 해보며 나름 완벽하다고 예상되게 코드를 짜보았다.
• 그러나 1284, 1793과 같은 숫자를 넣었을 때 오류가 발생하였고, 결국 모든 경우를 다 고려해보는 동적 프로그래밍(Dynamic Programming)으로 짜야한다는 것을 인정할 수밖에 없었다.

✔ 수정 후 코드

X = int(input())
dp = [-1, 0, 1, 1]

#점화식: dp[N] = min(dp[N-1], dp[N//2] , dp[N//3]) + 1

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

    dp.append(dp[i-1] + 1)

    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)

    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[X])

• 동적 프로그래밍(Dynamic Programming)을 사용해본 것은 처음이었기 때문에, 구글링의 도움을 조금 얻었다..
• 오히려 코드가 더 간결해지는 것을 보고 (물론 더 많은 케이스들을 고려해보는 코드이지만) 동적 프로그래밍이 나쁘지 않은 선택지라는 것을 깨달았다.
• 이 코드는 동적 프로그래밍 중에서도 작은 문제부터 차근차근 구해가는 Bottom-Up 방식이며, 각 숫자에서 3가지 연산 중 가능한 모든 경우를 비교해서 최솟값을 저장한다.

• 수정 전 코드를 아무리 보완해서 제출해도 틀리길래, 결국 모든 경우를 고려해보는 동적 프로그래밍을 사용하여 맞추었다.
  
  

처음으로 풀어본 DP 문제!

✔ 관련 개념

• 동적 프로그래밍 (Dynamic Programming): https://galid1.tistory.com/507