[BOJ] 1463번 1로 만들기

🔗 문제

https://www.acmicpc.net/problem/1463

📌 문제 요약

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

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

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

입력: 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력: 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

💡 접근 방법

문제 유형: 다이나믹 프로그래밍 (1차원 DP)

X를 3으로 나누는 경우,
X를 2로 나누는 경우,
X에 1을 빼는 경우 총 세가지 경우의 수가 있으며 가장 적은 횟수의 경우를 찾는 문제다.

왜 그리디가 아니라 DP인가?
“큰 수로 나눌수록 빨리 줄어드니까 3 → 2 → -1 순으로 욕심내면 되지 않나?” 싶지만 틀린다.
아래 다른 풀이와 비교에 반례를 적어뒀다.
지금 한 번 덜 유리해 보이는 선택이 나중에 더 좋은 길을 여는 경우가 있어서,
당장의 최선만으로는 전체 최솟값을 보장하지 못한다.

반면 부분 문제는 겹친다. 10을 1로 만드는 최소 횟수를 구하는 도중에도
5, 4, 3, 2를 1로 만드는 문제가 계속 다시 나온다.
“최적 부분 구조 + 겹치는 부분 문제” — DP의 두 조건이 그대로 성립한다.

그래서 정수 N까지 가는 과정에서 재사용할 것은 재사용하도록 구현 하게 되었다.

점화식

dp[i] = i를 1로 만드는 데 필요한 최소 연산 횟수

dp[1] = 0
dp[i] = min(
          dp[i - 1] + 1,                  // 항상 가능: 1을 뺀다
          dp[i / 2] + 1  (i % 2 == 0),    // 2로 나누어떨어질 때만
          dp[i / 3] + 1  (i % 3 == 0)     // 3으로 나누어떨어질 때만
        )

i보다 작은 값(i-1, i/2, i/3)만 참조하므로 1부터 N까지 순서대로 올라가면(바텀업)
필요한 값은 이미 다 계산돼 있다.

⚠️ 처음에 했던 실수

처음에 문제를 보고 모든 경우의 수를 찾고, 최솟값을 찾도록 구현 했었다.
브루트포스와 백트래킹을 합친 알고리즘으로 풀었는데 운이 좋았는지 풀려 정답인지 알았다.

문제는 같은 값을 몇 번이고 다시 계산한다는 것이다.
매 단계에서 최대 3갈래로 갈라지고 깊이가 O(log N)~O(N)까지 갈 수 있어서,
가지치기가 잘 먹히지 않는 입력에선 호출 횟수가 지수적으로 늘어난다.

고친 방향은 간단하다. 이미 구한 답은 배열에 적어두고 다시 쓰는 것.
그러면 각 값을 딱 한 번씩만 계산하므로 O(N)으로 떨어진다.

💻 코드

#include <iostream>
#include <cmath>
using namespace std;

int N;
int dp[1000001];

int main() {
    cin >> N;
    dp[1] = 0;   // 1은 이미 1이므로 연산 0번. 이게 유일한 기저 사례

    // 작은 수부터 채운다(바텀업).
    // i를 계산할 때 필요한 i-1, i/2, i/3은 전부 i보다 작으므로 이미 확정돼 있다.
    for(int i = 2; i <= N; ++i)
    {
        // 1 빼기는 언제나 가능하므로 이걸 기본값으로 깔고 시작한다
        dp[i] = dp[i - 1] + 1;

        // 나누어떨어질 때만 후보에 추가하고, 더 작은 쪽을 택한다
        if (i % 3 == 0)
            dp[i] = min(dp[i], dp[i / 3] + 1);

        if (i % 2 == 0)
            dp[i] = min(dp[i], dp[i / 2] + 1);

    }
    cout << dp[N];
    return 0;
}

⏱️ 시간·공간 복잡도

N ≤ 1,000,000

구간	복잡도	설명
DP 루프	O(N)	i마다 나눗셈 판정 2번 + `min` 2번 = 상수 시간
전체 시간	O(N)	최대 백만 번 반복
공간	O(N)	`int dp[1000001]` ≈ 4MB

dp[i]가 dp[i-1]만 참조했다면 변수 두 개로 O(1) 공간이 되겠지만,
dp[i/2]와 dp[i/3]은 한참 뒤의 값을 들춰봐야 해서 배열 전체를 들고 있어야 한다.
그래서 이 문제는 공간을 줄이기 어렵다.

참고로 dp를 전역에 두면 0으로 초기화된 상태로 시작한다.
main 안에 int dp[1000001]을 선언하면 스택에 4MB를 잡으려다 스택 오버플로가 날 수 있다.

🔀 다른 풀이와 비교

방식	시간	공간	메모
순수 브루트포스 / 백트래킹	지수적	O(log N)	같은 값을 계속 다시 계산한다. 처음에 짰던 코드
탑다운 재귀 + 메모이제이션	O(N)	O(N) + 재귀 스택	점화식을 그대로 옮길 수 있어 직관적. 대신 스택 깊이 주의
바텀업 DP (이 풀이)	O(N)	O(N)	재귀 없음, 상수도 가장 작다
BFS (1을 향한 최단 경로)	O(N)	O(N)	“연산 1회 = 간선 1개”로 보는 관점. N까지 안 가고 답을 찾으면 조기 종료 가능
그리디 (3 → 2 → -1 우선)	O(log N)	O(1)	오답

그리디가 틀리는 반례: N = 10

그리디 (2로 나눌 수 있으면 먼저 나눈다)
  10 → 5 → 4 → 2 → 1        연산 4번
       ÷2   -1   ÷2   ÷2

정답 (DP)
  10 → 9 → 3 → 1            연산 3번
       -1   ÷3   ÷3

10에서 일부러 1을 빼서 9를 만드는 것이 정답이다.
당장은 손해 보는 수처럼 보이지만 9가 3으로 두 번 나누어떨어지기 때문이다.
“지금 가장 크게 줄이는 선택”이 전체 최적이 아니라는 게 눈에 보이는 케이스라,
왜 DP가 필요한지 설명할 때 이 반례를 쓰면 편하다.

DeveloperOC

Contact