[백준/C++] 9095번: 1, 2, 3 더하기 - DP의 정석을 맛보다

1. 문제 정보

• 문제 번호: 9095번
• 문제 이름: 1, 2, 3 더하기
• 문제 요약: 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하라.

 

2. 고민의 흔적: 재귀에서 DP로

처음 이 문제를 보면 "모든 경우를 다 만들어봐야 하나?"라는 생각에 재귀 함수를 떠올리기 쉽다. 하지만 숫자가 커질수록 경우의 수가 기하급수적으로 늘어나기 때문에 중복 계산이 발생하고 효율성이 떨어진다.

여기서 필요한 사고의 전환이 바로 DP(다이내믹 프로그래밍)이다.

 

왜 이 문제가 DP인가? (중요 포인트!)

공부하면서 정리한 DP의 핵심 판단 기준 세 가지가 이 문제에 완벽히 들어맞는다.

1. 큰 문제를 작은 문제로 나눌 수 있다: n을 만드는 방법은 n-1, n-2, n-3을 만드는 방법들을 합친 것과 같다.
2. 작은 문제의 결과를 저장해두면 큰 문제를 쉽게 풀 수 있다: dp[1], dp[2], dp[3]의 값을 알면 dp[4]를 바로 구할 수 있다.
3. 중복 계산이 많아진다: 재귀로 풀면 같은 값을 구하는 함수가 반복적으로 호출되지만, DP는 한 번 구한 값을 배열에 저장(Memoization/Tabulation)해 재사용한다.

 

3. 점화식 유도 (Logic)

숫자 4를 만드는 경우를 생각해보자. 4를 만드는 마지막 단계는 세 가지 중 하나이다.

• 3을 만드는 방법에 1을 더하기: dp[3]의 모든 경우 뒤에 +1
• 2를 만드는 방법에 2를 더하기: dp[2]의 모든 경우 뒤에 +2
• 1을 만드는 방법에 3을 더하기: dp[1]의 모든 경우 뒤에 +3

따라서 점화식은 다음과 같다.

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

초기값(Base Case) 설정

• 1: (1) → 1개 (dp[1]=1)
• 2: (1+1, 2) → 2개 (dp[2]=2)
• 3: (1+1+1, 1+2, 2+1, 3) → 4개 (dp[3]=4)

 

4. 코드 구현

사용자가 제출한 코드는 상향식(Bottom-Up) 방식을 사용하고 있으며, 문제의 범위가 n < 11로 매우 작기 때문에 미리 배열을 다 채워놓고 출력하는 효율적인 방식을 택했다.

 

 

#include <iostream>
using namespace std;

int main() {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    int dp[11];
    
    // 초기값 설정
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;

    // 점화식을 이용해 4부터 10까지 미리 계산 (Tabulation)
    for(int i = 4; i < 11; i++){
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
    }
    
    cin >> n;
    // 테스트 케이스 수만큼 결과 출력
    for(int i = 0; i < n; i++){
        int number;
        cin >> number;
        cout << dp[number] << "\n";
    }
    
    return 0;
}

 

 

5. 배운 점 & 회고 (TIL) ✍️

① 규칙을 찾기 힘들 땐 직접 써보자

DP 문제의 점화식이 한눈에 보이지 않을 때는 n=1, 2, 3, 4, 5 정도까지 직접 손으로 써보는 것이 큰 도움이 된다. 나열하다 보면 피보나치 수열과 유사한 규칙성이 보이기 시작한다.

② "마지막 단계"를 생각하자

점화식을 세울 때 가장 강력한 팁은 "목표 지점에 도달하기 직전의 상태가 무엇인가?"를 고민하는 것이다. 1, 2, 3만 더할 수 있다면 직전 단계는 무조건 i-1, i-2, i-3일 수밖에 없다는 논리가 이 문제의 핵심이다.

③ DP의 강력함

재귀로 풀었다면 헷갈렸을 로직이 배열을 채우는 단순 반복문으로 해결되는 것을 보며, 왜 복잡한 문제일수록 자료구조와 알고리즘 선택이 중요한지 다시금 깨달았다.