[C++] 백준 10844번: 쉬운 계단 수 (DP)

10844번: 쉬운 계단 수

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

길이가 N인 계단 수의 총 개수를 1,000,000,000으로 나눈 나머지를 구하여라.

 

 여기서 계단 수란 121212와 같이 인접한 수의 차이가 1인 수를 말합니다.

---

시간복잡도 어림하기

브루트 포스 알고리즘

 현재 수가 1~8일 때, 다음에 올 수 있는 수는 2가지이고, 현재 수가 0과 9일 때에는 다음에 올 수 있는 수가 1가지입니다. 정확한 계산은 아니지만 지수 형태의 시간복잡도를 가질 것이라 예측할 수 있습니다. 문제에서 N의 최댓값은 100이므로 제한 시간 내에 문제를 해결하기 어렵습니다.

 

DP 알고리즘

 계단 수에 길이에 따른 상태를 배열에 모두 저장할 수 있고, 아래 그림과 같이 계단수를 찾아보면 비슷한 구조가 반복된다는 것을 알 수 있습니다. 따라서 이 중복된 연산을 제거하는 방향으로 DP를 구성하면 문제를 해결할 수 있을 것입니다. 

 동일한 연산을 제외한다면 연산 횟수는 계단 수의 길이 * 10(0부터 9까지를 의미) 이므로 최대 100 * 10 = 1000번의 연산으로 문제를 해결할 수 있습니다.

---

알고리즘 설계하기

 시간복잡도 어림 단계에서 봤던 그림을 다시 살펴봅시다. 그림을 잘 살펴보면, 동일한 트리의 높이에서 같은 숫자라면 그보다 낮은 높이의 값은 모두 동일한 것을 확인할 수 있습니다. 따라서 다음과 같이 규칙을 정리할 수 있습니다.

트리의 높이가 같을 때, 트리의 값도 동일하다면 동일한 자식 노드를 가진다.

여기서 변수가 될 수 있는 값은 "트리의 높이"와 "트리의 값" 이므로 dp[높이(길이)][현재 수]로 dp 배열을 구성할 수 있습니다.

 

 이제 경우의 수를 생각해봅시다.

1. 계단 수의 길이가 1일 때, 경우의 수는 0을 제외한 9개이다.
2. 계단 수의 길이가 2이상일 때,
 2.1 현재 수가 0일 때, 이전 길이의 1의 값과 같다.
 2.2 현재 수가 9일 때, 이전 길이의 8의 값과 같다.
 2.3 현재 수가 0도 9도 아닐 때, 이전 길이의 현재 수 - 1, 현재수 + 1의 값을 더한 것과 같다.

 

 간단히 코드로 나타내 보면,

if(현재 수 == 0) dp[현재 길이][0] = dp[현재 길이 - 1][1];
if(현재 수 == 9) dp[현재 길이][9] = dp[현재 길이 - 1][8];
for(int i = 2; i <= 8; i++)
	dp[현재 길이][i] = dp[현재 길이 - 1][i - 1] + dp[현재 길이 - 1][i + 1];

다음과 같이 나타낼 수 있습니다. 위 과정을 길이가 1일 때부터 N까지 반복하면 문제를 해결할 수 있습니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#define DIV 1000000000
using namespace std;

typedef long long ll;
ll n, dp[104][10], ret;
int main(){
    cin >> n;
    
    /*길이가 1일 때의 값 초기화*/
    for(int i = 1; i < 10; i++) dp[1][i] = 1;
    
    for(int i = 2; i <= n; i++){
        dp[i][0] = dp[i - 1][1] % DIV; //현재 수가 0일 때
        dp[i][9] = dp[i - 1][8] % DIV; //현재 수가 9일 때
        for(int j = 1; j <= 8; j++)
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % DIV;
    }
    
    /*모든 경우의 수 합산*/
    for(int i = 0; i < 10; i++){
        ret += dp[n][i] % DIV;
    }
    cout << ret % DIV;
    return 0;
}

 핵심 로직은 설계단계에서 이야기한 것과 동일합니다. 주의해야할 것은 문제에서 경우의 수를 1,000,000,000으로 나눈 나머지를 계산하라고 했으므로 mod 연산을 누적하여 값을 계산했습니다. mod 연산에 대해 잘 모르시는 분들은 한 번 검색해 해보는 것을 추천합니다.

 

다른 코드(브루트 포스에서 중복 연산 제거)

#include<iostream>
#define DIV 1000000000
using namespace std;

typedef long long ll;

ll n, dp[104][10], ret;
ll solve(int idx, int num){
	/*기저 사례(리프 노드 도달)*/
    if(idx == n) return 1;
    ll &rt = dp[idx][num];
    if(rt > 0) return rt; //이미 계산된 경우의 수일 때
    
    if(num == 0) rt = solve(idx + 1, num + 1) % DIV;
    else if(num == 9) rt = solve(idx + 1, num - 1) % DIV;
    else rt = (solve(idx + 1, num + 1) + solve(idx + 1, num - 1)) % DIV;
    return rt;
}

int main(){
    cin >> n;
    for(int i = 1; i <= 9; i++)
        ret += solve(1, i) % DIV;
    cout << ret % DIV;
    return 0;
}

 핵심 알고리즘은 이전 코드와 유사하지만, 재귀적 호출을 통해 문제를 해결하는 코드입니다. 반복을 통한 dp 갱신 알고리즘을 떠올리기 어려우신 분들은 위 코드처럼 재귀적으로 함수를 호출하고, 중복된 연산을 제거하는 방향으로 아이디어를 떠올리는 것이 좋습니다.

---