정수를 1로 만들기란?
정수 X가 하나 주어졌을 때, 다음 세 가지 연산만으로 X를 1로 만드는 최소 연산 횟수를 구하는 문제입니다.
- •÷3 — X가 3의 배수일 때만, 3으로 나눕니다.
- •÷2 — X가 짝수일 때만, 2로 나눕니다.
- •−1 — X에서 1을 뺍니다.
알고노트에서는 이 문제를 "장난감 가게의 마법 카운터를 최소 버튼 클릭으로 1로 만들기"라는 이야기로 시각화합니다.
왜 그리디는 틀릴까?
"가능한 한 크게 나누면 빠르겠지"라는 직관(그리디)은 이 문제에서 틀립니다.
X = 10을 봅시다.
- •그리디(짝수니까 ÷2 먼저): 10 → 5 → 4 → 2 → 1 = 4번
- •정답: 10 → 9(−1) → 3(÷3) → 1(÷3) = 3번
먼저 −1을 해서 9로 만들면 ÷3을 두 번 쓸 수 있습니다. 눈앞의 큰 나눗셈이 항상 최선은 아니라는 것, 이것이 DP가 필요한 이유입니다.
DP 점화식
dp[i]를 "i를 1로 만드는 최소 연산 횟수"로 정의합니다.
- •기저 조건:
dp[1] = 0(이미 1이라 연산 불필요) - •점화식:
dp[i] = 1 + min(
dp[i - 1], // −1 (항상 가능)
dp[i / 2] if i % 2 == 0, // ÷2 (짝수일 때만)
dp[i / 3] if i % 3 == 0 // ÷3 (3배수일 때만)
)i를 1로 만드는 마지막 직전 상태는 i-1, i/2, i/3 중 하나입니다. 그 각각의 최소 횟수에 1(이번 연산)을 더한 값 중 가장 작은 것을 고릅니다.
동작 원리
1단계. dp[1] = 0으로 시작하고 나머지는 ∞(아직 모름)로 둡니다.
2단계. 2부터 X까지 작은 수부터 차례로 채웁니다. dp[i]를 계산할 때 필요한 dp[i-1], dp[i/2], dp[i/3]은 모두 이미 확정되어 있습니다.
3단계. dp[X]가 최종 정답입니다.
시간복잡도와 공간복잡도
| 복잡도 | |
|---|---|
| 시간 | O(X) |
| 공간 | O(X) |
각 i를 한 번씩만 계산하고, 매번 상수 개(최대 3개)의 후보만 비교하므로 전체 O(X)입니다.
자주 하는 실수
- •인덱스 0 처리:
dp[1] = 0이 기저 조건입니다. 0은 사용하지 않습니다. - •나눗셈 조건 누락: ÷2는 짝수일 때만, ÷3은 3배수일 때만 후보로 넣어야 합니다.
- •그리디로 풀기: 위 예시처럼 큰 나눗셈 우선 그리디는 반례가 존재합니다. 반드시 DP로 모든 작은 수의 최적해를 저장하세요.
알고노트에서 직접 확인하세요
각 칸 dp[i]가 어떤 연산(−1 / ÷2 / ÷3)으로 최소가 되는지, 알고노트 시각화에서 한 단계씩 따라가 보세요. 시작 숫자를 바꿔가며 그리디가 언제 함정에 빠지는지 실험해볼 수 있습니다.