[BOJ] 1463. 1로 만들기

📌 문제 제목

문제 링크: BOJ 1463

---

🗒️ 문제 설명

정수 X가 할 수 있는 연산

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

정수 N을 1로 만들려고 할 때, 연산의 최솟값을 구하여라.

시간 제한: 1.5초

메모리 제한: 128MB

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

---

💡 문제 해결 아이디어

• N이 최대 1,000,000이기 때문에 시간복잡도가 O(N)이하의 알고리즘을 사용
• 연산 횟수를 저장할 N+1 길이의 배열을 만들어서 사용
• BFS와 DP를 사용하면 풀 수 있다.

# BFS 사용

• -1을 가지는 N+1 길이의 dist 배열 정의
• dist[N] = 0으로 초기화
• queue에 N을 넣고 BFS 수행
• queue를 popleft()해서 xp를 구한 후 위의 세 연산을 수행한 값이 integer라면 dist[res] = dist[xp] + 1
• BFS는 xp가 1일 때까지 수행

 

# DP 사용

• 테이블 정의
  • -1을 가지는 N+1 길이의 dist 배열 정의
• 점화식 찾기
  • n이 3으로 나누어 떨어지면 cnt[n] = cnt[n // 3] + 1
  • n이 2로 나누어 떨어지면 cnt[n] = cnt[n // 2] + 1
  • 1을 뺀 값 cnt[n] = cnt[n-1] + 1
  • 위의 세 값 중 가장 작은 값이 cnt[n]이 된다.
• 초기값 정하기
  • dist[1] = 0

---

⌛️ 시간 복잡도

• O(N)

---

✅ 최종 코드

시간 복잡도는 같지만 BFS가 더 빨랐음.

이해하기에도 BFS가 더 좋은듯

# use BFS

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

N = int(input().strip())

dist = [-1] * (N + 1)
dist[N] = 0

queue = deque([N])
while queue:
    xp = queue.popleft()
    if xp == 1:
        break
    for res in [xp/3, xp/2, xp-1]:
        if int(res) != res:
            continue
        res = int(res)
        if dist[res] == -1:
            dist[res] = dist[xp] + 1
            queue.append(res)

print(dist[1])

# use DP

import sys
input = sys.stdin.readline

N = int(input().strip())

dist = [-1] * (N+1)
dist[1] = 0

for i in range(2, N+1):
    d3, d2, d1 = float("inf"), float("inf"), dist[i-1] + 1

    if i % 3 == 0:
        d3 = dist[i // 3] + 1
    if i % 2 == 0:
        d2 = dist[i // 2] + 1
    dist[i] = min(d3, d2, d1)
print(dist[N])