[백준/Python] 12852. 1로 만들기 2 - DP

본 포스팅은 해당 문제를 1차원 배열의 DP로 푼 풀이에 대해 정리하였다.
그러나 BFS로도 쉽게 풀 수 있기 때문에 아래 포스팅도 참고 바란다.

해당 문제는 어렵지 않아 BFS와 DP 모두 간단하게 풀 수 있지만, 난이도가 올라갈수록 DP는 보통 다른 알고리즘들로 풀 수 없을 때 활용하는 최후의 방안이기 때문에 BFS로 푸는 방법을 모른다면 아래 포스팅을 꼭 공부해보기를 추천한다.

📋 참고 포스팅:[백준/Python] 12852. 1로 만들기 2

---

📄 문제

백준
난이도 : Silver 1
문제 제목 : 1로 만들기 2

✏️ 풀이 1

import sys

n = int(sys.stdin.readline())

if n == 1:
    print(0)
    print(1)
    sys.exit(0)
elif n < 3:
    print(1)
    print(2, 1)
    sys.exit(0)

d = [0] * (n + 1)
pre = [0] * (n + 1)
d[2] = 1
pre[2] = 1
d[3] = 1
pre[3] = 1

for i in range(4, n + 1):
    d[i] = d[i - 1] + 1
    pre[i] = i - 1
    if not i % 2 and d[i] > d[i // 2] + 1:
        d[i] = d[i // 2] + 1
        pre[i] = i // 2
    if not i % 3 and d[i] > d[i // 3] + 1:
        d[i] = d[i // 3] + 1
        pre[i] = i // 3
        
print(d[n])
route = n
while curr:
    print(route, end=' ')
    route = pre[curr]

✅ 풀이 한줄 설명:
DP로 풀 수 있는 문제이다. 위 풀이는 DP 테이블을 다음과 같이 정의한 풀이이다.
d[i] = i를 1로 만드는 최소 연산 횟수

더해서, 현재 숫자(i)가 어떤 숫자(이전 방문한 숫자)로부터 왔는지를 경로 배열에 기록한다.

✅ 풀이 자세한 설명:
DP 문제는 다음과 같이 풀이를 진행하는 것이 좋다.

• 테이블 정의하기
• 점화식 찾기
• 초기값 정의하기

그리고 경로 복원용 테이블(pre)을 두어 직전에 방문한 수를 저장하도록 한다.

🍎 1. 테이블 정의하기
d[i] = i를 1로 만드는 최소 연산 횟수
pre[i] = i 이전에 방문했던 숫자

🍎 2. 점화식 찾기
d[k]와 pre[k]는 다음과 같이 정의 가능하다.
(참고로 아래에서 말하는 '후보군'은 d[k // 3] + 1, d[k // 2] + 1, d[k - 1] + 1 이 세 가지이다.)

• k가 3으로 나누어지고 d[k // 3] + 1 이 후보군 중 가장 작으면
  -> d[k] = d[k // 3] + 1, pre[k] = k // 3
• k가 2로 나누어지고 d[k // 2] + 1 이 후보군 중 가장 작으면
  -> d[k] = d[k // 2] + 1, pre[k] = k // 2
• d[k - 1] + 1 이 후보군 중 가장 작으면
  -> d[k] = d[k - 1] + 1, pre[k] = k - 1

🍎 3. 초기값 정의하기
d[1] = 0, pre[1] = 0
d[2] = 1, pre[2] = 1
d[3] = 1, pre[3] = 1

📦 GitHub

해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Silver) '12852. 1로 만들기 2'
GitHub - [16강] 시뮬레이션/연습문제 '12852. 1로 만들기 2'

---

💫 이 문제와 같이 거쳐온 과정(경로)을 출력하라고 하는 경우, 경로 복원용 테이블 배열을 두는 것을 추천한다.