[BOJ] 12852. 1로 만들기 2

📌 문제 제목

문제 링크: BOJ 12852

---

🗒️ 문제 설명

정수 X에 사용할 수 있는 연산

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

세 개의 연산을 사용해 정수 N을 1로 만들려고 할 때, 연산을 사용하는 횟수의 최솟값을 구하여라.

출력에는 연산을 하는 횟수의 최솟값과 N을 1로 만드는데 포함되어있는 수를 공백으로 구분해서 출력

시간 제한: 0.5초

메모리 제한: 512MB

1 <= N <= 10^6 (1,000,000)

---

💡 문제 해결 아이디어

• BFS와 DP를 사용하여 해결 가능

# BFS 사용

• dist[i]는 N을 i로 만들려고 할 때, 연산의 최솟값.
• prev[i]는 N을 i로 만들려고 할 때, i 직전에 들러야 하는 값

# DP 사용

• 테이블 정의
  • dp[i]는 1을 i로 만들려고 할 때, 연산의 최솟값
  • prev[i]는 1을 i로 만들려고 할 때, i 직전에 들러야 하는 값
• 점화식 찾기
  • min 사용 못함
    • min을 사용하면 최솟값은 알 수 있지만, 어디에서 이 경로로 왔는지 알 수 없음.
  • 1칸 빼기
    • dp[i] = dp[i-1] + 1
    • prev[i] = i-1
  • 2로 나누어 떨어짐
    • dp[i] = dp[i//2] + 1
    • prev[i] = i // 2
  • 3으로 나누어 떨어짐
    • dp[i] = dp[i//3] + 1
    • prev[i] = i // 3

---

⌛️ 시간 복잡도

• O(N)

---

✅ 최종 코드

import sys
from collections import deque
input = sys.stdin.readline

n = int(input().strip())
visited = [False] * (n + 1)
prev = [0] * (n + 1)

queue = deque()
queue.append(n)
visited[n] = True

while queue:
    cur = queue.popleft()

    if cur == 1:
        break

    for nxt in [cur // 3, cur // 2, cur - 1]:
        if (cur % 3 == 0 and nxt == cur // 3) or (cur % 2 == 0 and nxt == cur // 2) or nxt == cur - 1:
            if not visited[nxt]:
                visited[nxt] = True
                prev[nxt] = cur
                queue.append(nxt)

path = []
cur = 1
while cur != 0:
    path.append(cur)
    cur = prev[cur]
path.reverse()

print(len(path) - 1)
print(" ".join(map(str, path)))

# use DP
import sys
input = sys.stdin.readline

n = int(input().strip())
dp = [0] * (n + 1)
prev = [0] * (n + 1)

for i in range(2, n + 1):
    dp[i] = dp[i - 1] + 1
    prev[i] = i - 1

    if i % 2 == 0 and dp[i // 2] + 1 < dp[i]:
        dp[i] = dp[i // 2] + 1
        prev[i] = i // 2

    if i % 3 == 0 and dp[i // 3] + 1 < dp[i]:
        dp[i] = dp[i // 3] + 1
        prev[i] = i // 3

print(dp[n])

path = []
cur = n
while cur != 0:
    path.append(cur)
    if cur == 1:
        break
    cur = prev[cur]
print(prev)
print(*path)