[DP] 백준 1463. 1로 만들기

오늘은 DP 2번째 문제 1로 만들기입니다.

---

1. 문제: 백준 1463. 1로 만들기

• 단계: 🥈실버 3단계
• 주제:
  • 다이내믹 프로그래밍
• 출처: https://www.acmicpc.net/problem/1463

문제

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

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

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

입력

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

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

---

2. 문제 풀이

처음엔 완전 탐색이 떠올랐지만, N이 최대 10^6까지 주어지기 때문에 완전 탐색은 비효율적입니다.

이 문제는 DP 개념을 적용해서 중복 계산을 줄이고, 최적해를 효율적으로 구할 수 있는 문제입니다.

그래서 다음의 세 가지 방식으로 구현해보았습니다:

완전 탐색 풀이

def dfs(N, cnt):
    # 1. base case
    if N == 1:
        return cnt
    
    res = dfs(N - 1, cnt + 1)

    if N % 2 == 0:
        res = min(res, dfs(N // 2, cnt + 1))
    if N % 3 == 0:
        res = min(res, dfs(N // 3, cnt + 1))
    
    return res

def main():
    N = int(input().strip())

    print(dfs(N, 0))

if __name__ == '__main__':
    main()

Top-Down DP 풀이

import sys
sys.setrecursionlimit(10 ** 6)
def dfs(N):
    global memo

    # 1. base case
    if N == 1:
        return 0
    
    if N in memo:
        return memo[N]
    
    res = dfs(N - 1) + 1

    if N % 2 == 0:
        res = min(res, dfs(N // 2) + 1)
    if N % 3 == 0:
        res = min(res, dfs(N // 3) + 1)
    
    memo[N] = res
    return memo[N]

def main():
    global memo
    N = int(input().strip())
    memo = {}
    print(dfs(N))

if __name__ == '__main__':
    main()

Bottom-Up DP 풀이

def dfs(N):
    tab = [0] * (N + 1)

    for i in range(2, N + 1):
        tab[i] = tab[i - 1] + 1

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

    return tab[N]

def main():
    N = int(input().strip())
    print(dfs(N))

if __name__ == '__main__':
    main()

 

---

3. 마무리

이번 문제는 DP의 기본기와 개념 전환이 정말 중요했던 문제였습니다.

처음엔 단순하게 탐색으로 풀 수 있을 것 같지만,

입력의 범위가 크기 때문에 반드시 중복 연산을 줄이는 최적화 기법이 필요합니다.

이 문제를 풀면서 "아, 그래서 DP가 필요한 거구나!"라는 걸 몸소 느낄 수 있었습니다.

앞으로 DP 문제들을 볼 때 입력 범위, 중복 호출 여부, 최적화 가능성을 꼭 고려해야겠다는 교훈을 얻었습니다.

읽어주셔서 감사합니다!