풀이가 틀리고, 처음에는 단순한 코딩 오류라고 생각했던 것이, 사실은 문제 해석 자체에 있었다는 것을 깨닫는 과정이었습니다. DP의 원리와 함께, 흔히 겪는 함정을 어떻게 극복할 수 있는지 공...

10844번 계단 수 문제, DP

풀이가 틀리고, 처음에는 단순한 코딩 오류라고 생각했던 것이, 사실은 문제 해석 자체에 있었다는 것을 깨닫는 과정이었습니다. DP의 원리와 함께, 흔히 겪는 함정을 어떻게 극복할 수 있는지 공부했습니다. 이를 공유하고자 합니다.

학습 주제

오늘 공부한 주제: 10844번 계단 수 문제 DP 풀이 및 오답 원인 분석
대화 제목: 10844번 dp 시행착오와 풀이 성공까지
학습 날짜: 2026년 2월 12일

질문과 탐구

이번 학습은 1e9와 long long의 타입 문제, 그리고 long long의 최대값 등에 대한 궁금증에서 시작되었습니다. 특히 C++에서 과학적 표기법 e의 타입이 double이라는 점, 그리고 long long으로 값을 대입할 때 발생할 수 있는 암묵적 형변환의 위험성을 알게 되었습니다.

하지만 진짜 탐구는 제가 작성한 계단 수 DP 코드가 왜 틀렸는지를 파헤치면서 시작되었습니다. 저는 dp[i] = 2*(dp[i-1] - 2) + 2라는 점화식으로 접근했지만, AI는 이 점화식이 문제를 잘못 모델링했다고 지적했습니다. 전체 개수만 세는 DP로는 마지막 자릿수라는 중요한 상태를 보존하지 못한다는 것이 핵심이었습니다.

이후 저는 점화식을 수정하고, dp[i] = (((2*(dp[i-1] - 2)) + 2) - dp[i-1]) % mod; 와 같이 보정해보기도 했지만, 이는 오히려 dp[i] = dp[i-1] - 2와 같은 의미 없는 수열을 만드는 결과를 낳았습니다. AI는 이 과정이 수치 튜닝이지 수학적 해결이 아니라고 지적하며, 상태 정의 자체를 다시 해야 한다고 강조했습니다.

결정적으로, 제가 dp[n][d]를 "계단 수의 개수"가 아닌 "그래프 경로의 개수"로 착각하고 있다는 점을 파고들었습니다. 이 혼동이 초기값 오류, 경계 처리 누락, 마지막 모듈러 누락이라는 세 가지 구체적인 코드 문제로 이어졌다는 것을 알게 되었습니다.

핵심 학습 내용

DP 문제 해결에서 가장 중요한 몇 가지 개념을 명확히 배울 수 있었습니다.

상태 정의의 중요성: DP는 결국 "상태"를 어떻게 정의하느냐에 달려있습니다. 계단 수 문제의 경우, 단순히 총합을 세는 것이 아니라 '마지막 자릿수'라는 상태를 명시적으로 관리해야 했습니다. dp[i][d]는 길이가 i이고 마지막 숫자가 d인 계단 수의 개수를 나타내야 했습니다.
그래프 탐색 vs. 조합론적 문제: 문제를 그래프 탐색 문제처럼 시각화하는 것은 직관적일 수 있지만, 때로는 조합론적 문제의 본질을 흐릴 수 있습니다. "경로의 개수"를 세는 것과 "조건을 만족하는 객체(문자열, 수열 등)의 개수"를 세는 것은 미묘하지만 결정적인 차이가 있습니다. 전자는 이동 횟수에 집중하는 반면, 후자는 결과물의 개수에 집중합니다.
초기값, 경계 처리, 모듈러 연산: DP 코드 구현 시 흔히 놓치기 쉬운 디테일들입니다.
- 초기값: 문제의 가장 작은 단위(여기서는 1자리 계단 수)에 대한 올바른 상태 값을 설정해야 합니다.
- 경계 처리: 배열의 범위를 벗어나지 않도록 d=0이나 d=9와 같은 경계 조건에서 특별한 처리가 필요합니다.
- 모듈러 연산: 값이 커질 경우 오버플로우를 방지하기 위해 각 단계마다 모듈러 연산을 적용해야 합니다.

예시 코드 (성공 버전)

#include<bits/stdc++.h>
using namespace std;
long long mod = 1000000000LL; // 모듈러 상수

long long dp[101][10]; // dp[n][d]: 길이가 n이고 마지막 숫자가 d인 계단 수의 개수

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

    int N;
    cin >> N; // 계단 수의 길이 입력

    // 1층(길이 1) 초기값 설정
    // 1자리 계단 수는 1, 2, ..., 9 각각 1개씩 존재
    for(int i = 1; i <= 9; i++){
        dp[1][i] = 1LL;
    }
    // dp[1][0]은 0으로 시작하는 계단 수가 없으므로 0 (기본값으로 자동 초기화)

    // dp 배열 채우기: n층 (길이 n)의 d로 끝나는 계단 수 계산
    for(int n = 2; n <= N; n++){
        for(int d = 0; d <= 9; d++){
            if(d == 0){ // 마지막 숫자가 0이면, 이전 숫자는 1이어야 함
                dp[n][0] = dp[n-1][1];
            }
            else if(d == 9){ // 마지막 숫자가 9이면, 이전 숫자는 8이어야 함
                dp[n][9] = dp[n-1][8];
            }
            else{ // 그 외의 경우(1~8), 이전 숫자는 d-1 또는 d+1 이어야 함
                dp[n][d] = (dp[n-1][d-1] + dp[n-1][d+1]) % mod;
            }
        }
    }

    long long sum = 0; // 최종 결과 합산

    // N층까지의 모든 계단 수 합산 (마지막 숫자가 0~9인 경우 모두 더함)
    for(int d = 0; d <= 9; d++){
        sum = (sum + dp[N][d]) % mod;
    }
    cout << sum; // 결과 출력
}

이해한 내용

이 과정을 통해 저는 DP 문제를 풀 때 다음과 같은 점들을 더 깊이 이해하게 되었습니다.

'경로'와 '객체'의 차이: 그래프에서 '경로'를 세는 것과, 주어진 조건을 만족하는 '객체'(여기서는 계단 수를 나타내는 문자열)의 개수를 세는 것은 근본적으로 다르다는 것을 명확히 알게 되었습니다. 그래프 사고방식은 '이동'에 집중하지만, 조합론적 사고방식은 '결과물' 자체에 집중합니다.
DP는 수학적 정의: DP는 결국 수학적 정의를 바탕으로 이루어져야 합니다. dp[n][d]는 'n번째 상태에서 d라는 경로를 따른다'가 아니라, 'n번째까지 만들어진 결과 객체 중 d라는 특성을 가진 것의 개수'로 이해해야 합니다.
실수로부터 배우기: 처음에는 제 코드가 논리적으로 틀렸다는 사실을 받아들이기 어려웠지만, AI의 명확한 설명과 단계별 해부 덕분에 근본적인 오류 지점을 파악할 수 있었습니다. 특히 dp[1][i] = 2와 같은 초기값 오류가 "그래프에서 out-degree가 2"라는 오해에서 비롯되었음을 깨닫고는, 사고의 전환이 얼마나 중요한지 절감했습니다.

실전 적용

이번 학습 내용은 앞으로 DP 문제를 풀 때 큰 도움이 될 것입니다.

문제 해석 능력 향상: 앞으로 DP 문제를 접했을 때, 가장 먼저 "이 문제는 '시스템 시뮬레이션'인가, 아니면 '수학적 객체의 개수 세기'인가?"라는 질문을 던질 것입니다. 이를 통해 문제의 본질을 파악하고 올바른 상태 정의를 내리는 데 집중할 수 있을 것입니다.
코드 실습 계획:
- 다른 유형의 DP 문제(예: 오르막 수, 감소 수)를 풀어보며 '객체 세기' DP 접근 방식을 익힐 것입니다.
- 그래프 탐색 DP와 조합론 DP의 차이를 명확히 구분하는 연습을 할 것입니다.
응용 아이디어: DP는 경우의 수 계산뿐만 아니라 최적화 문제에도 많이 사용됩니다. 이번 학습에서 얻은 '상태 정의'의 중요성은 복잡한 최적화 문제에서도 올바른 DP 모델을 설계하는 데 기여할 것입니다.

추가 학습 계획

다양한 DP 패턴 학습: 이번 문제에서 겪었던 '상태 압축의 함정'과 같은 패턴을 더 깊이 이해하기 위해, 다양한 DP 문제들을 풀어보며 다른 패턴들을 학습할 계획입니다. 특히 2차원 DP에서 1차원 DP로 공간 최적화를 할 때 주의해야 할 점들을 집중적으로 공부하고 싶습니다.
관련 자료:
- 백준 알고리즘 사이트의 DP 관련 문제 풀이
- DP 개념을 쉽게 설명하는 알고리즘 강의 자료 (유튜브, 온라인 강의)
- 'DP State Definition' 관련 해외 블로그 글