[Baekjoon/Python] 1463. 1로 만들기 (DP)

mj·2025년 11월 3일

코딩테스트문제

목록 보기

61/64

✅ 문제 정의

정수 X가 주어졌을 때, 다음 세 가지 연산을 적절히 사용하여 1을 만드는 연산 횟수의 최솟값을 구하는 문제이다.

3으로 나누기: X가 3으로 나누어 떨어질 때 (X → X / 3)
2로 나누기: X가 2로 나누어 떨어질 때 (X → X / 2)
1 빼기: (X → X - 1)

✅ 풀이 과정

Greedy의 실패와 DP의 필요성

나의 첫 번째 시도: Greedy 접근

아이디어: 연산 횟수를 최소화하려면 한 번에 가장 큰 폭으로 숫자를 줄여야 한다고 생각했다. 따라서, 나누기가 가능하다면 나누기를 우선적으로 시도하고, 나누기가 불가능할 때만 1을 빼는 Greedy(탐욕) 방식을 생각했다.
반례를 통한 실패 확인 (N=10):
- Greedy 방식 (나의 풀이): 10 - 5 - 4 - 2 - 1
  10은 3으로 안 나누어지므로 2로 나눔 → 10 -> 5 (1회) → 5는 2나 3으로 안 나누어지므로 1 뺌 → 5 -> 4 (2회) → 4를 2로 나눔 → 4 -> 2 (3회) → 2를 2로 나눔 → 2 -> 1 (4회) (총 4회)
- 최적 해: 10 - 9 - 3 - 1
  10을 1 뺌 → 10 -> 9 (1회) → 9를 3으로 나눔 → 9 -> 3 (2회) → 3을 3으로 나눔 → 3 -> 1 (3회) (총 3회)
결론: Greedy 방식은 당장 가장 이득인 선택을 하지만, 전체 과정을 봤을 때 최적의 해답을 보장하지 못한다. 이 문제는 "최소 횟수"를 구해야 하므로, 모든 가능성을 탐색하여 그중 최솟값을 찾는 Dynamic Programming (동적 계획법) 기법을 사용해야 한다.

핵심 개념: Dynamic Programming (동적 계획법)

동적 계획법(Dynamic Programming, DP)이란 복잡한 문제를 더 작은 하위 문제(Subproblem)로 나누어 해결하는 알고리즘 설계 기법이다.

특징	설명
최적 부분 구조	큰 문제의 최적 해가 그 하위 문제들의 최적 해로부터 구성될 수 있어야 합니다. (예: 10의 최소 연산 횟수는 9, 5, 3의 최소 연산 횟수에 1을 더한 값 중 최솟값으로 결정됩니다.)
중복되는 하위 문제	동일한 하위 문제가 반복적으로 계산되는 구조를 가집니다. (DP는 이 중복 계산 결과를 저장(Memoization 또는 Tabulation)하여 재사용함으로써 성능을 극대화합니다.)

이 문제에서는 $D[i]$ 를 "정수 $i$ 를 1로 만드는 최소 연산 횟수"라고 정의하고,
작은 값부터 차례로 $D[i]$ 를 채워나가는 상향식(Bottom-up) 접근법을 사용한다.

점화식 (Recurrence Relation)

D[i] = \min \begin{cases} D[i-1] + 1 & \text{(항상 가능)} \\ D[i/3] + 1 & \text{(i가 3의 배수일 때)} \\ D[i/2] + 1 & \text{(i가 2의 배수일 때)} \end{cases}

💡 점화식이란?
점화식은 이전 단계의 결과값을 이용해 현재 값을 계산하는 규칙이다.
즉, 큰 문제를 더 작은 문제로 나누어 푸는 동적 계획법(DP)의 핵심 개념이다.
예를 들어, 피보나치 수열의 F(n) = F(n-1) + F(n-2)처럼 “현재 값을 이전 값들로 표현하는 식”이 바로 점화식이다.

✅ 최종 코드

n = int(input())
d = [0] * (n + 1)	

for i in range(2, n + 1):
    d[i] = d[i - 1] + 1  # 1. 일단 1을 뺀 경우를 최솟값으로 설정

    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)  # 2. 3으로 나눈 경우가 더 작으면 교체
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)  # 3. 2로 나눈 경우가 더 작으면 교체

print(d[n])

코드 해설 분석: '1을 빼는 연산'을 먼저 하는 이유

제시된 파이썬 코드는 위 점화식을 그대로 구현한다.

for i in range(2, n + 1):
    d[i] = d[i - 1] + 1  # (1) 1을 뺀 경우를 일단 최솟값(후보)으로 설정
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1) # (2) 3으로 나눈 경우와 비교하여 갱신
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1) # (3) 2로 나눈 경우와 비교하여 갱신

질문: 처음에 왜 d[i] = d[i - 1] + 1로 1을 빼는 연산을 먼저 하고 시작하는가?

초기 최솟값 설정 (Initialization):
$i \to i-1$ 연산은 $i \ge 2$ 인 모든 수에 대해 항상 가능한 연산이다.
따라서, $i$ 의 최소 연산 횟수 $D[i]$ 는 적어도 $D[i-1] + 1$ 보다는 작거나 같을 것이 보장된다. 이 값을 초기 최솟값(최소 횟수의 후보)으로 설정하고 시작하는 것이다.
모든 경우 시도 보장: 이후 if i % 3 == 0이나 if i % 2 == 0 조건문이 실행될 때, 현재 $d[i]$ 에 저장된 1을 뺀 횟수와 나눈 횟수를 min() 함수로 비교하여 더 작은 값으로 갱신한다.
- 만약 3으로 나누는 것이 1을 빼는 것보다 더 빠르면: $D[i]$ 는 $D[i/3] + 1$ 로 갱신된다.
- 만약 2로 나누는 것이 현재 $D[i]$ 값(이미 3으로 나누거나 1을 뺀 값일 수 있음)보다 더 빠르면: $D[i]$ 는 $D[i/2] + 1$ 로 다시 갱신된다.

결론적으로, 이 코드는 세 가지 연산 $i \to i-1, i \to i/3, i \to i/2$ 을 모두 시도하고, 그중 최소 횟수를 $d[i]$ 에 저장하는 과정이며, 1을 빼는 연산은 세 가지 경우 중 가장 먼저 계산되는 기준 값일 뿐이다.