백준 No.10844 [쉬운 계단 수]

// Baekjoon Online Judge No.10884 [쉬운 계단 수]

---

   Code   

#include <iostream>
#include <vector>
 
using namespace std;
 
int N;
 
int main() {
    cin >> N;
 
    vector<vector<unsigned long long>> SN;
    SN.assign(10, vector<unsigned long long>(N + 1, 1));
 
    SN[0][1] = 0;
 
    for (int i = 2; i <= N; i++) {
        SN[0][i] = (SN[1][i - 1]) % int(1e9);
        SN[1][i] = (SN[0][i - 1] + SN[2][i - 1]) % int(1e9);
        SN[2][i] = (SN[1][i - 1] + SN[3][i - 1]) % int(1e9);
        SN[3][i] = (SN[2][i - 1] + SN[4][i - 1]) % int(1e9);
        SN[4][i] = (SN[3][i - 1] + SN[5][i - 1]) % int(1e9);
        SN[5][i] = (SN[4][i - 1] + SN[6][i - 1]) % int(1e9);
        SN[6][i] = (SN[5][i - 1] + SN[7][i - 1]) % int(1e9);
        SN[7][i] = (SN[6][i - 1] + SN[8][i - 1]) % int(1e9);
        SN[8][i] = (SN[7][i - 1] + SN[9][i - 1]) % int(1e9);
        SN[9][i] = (SN[8][i - 1]) % int(1e9);
    }
 
    unsigned long long ans = (SN[0][N] + SN[1][N] + SN[2][N] +
        SN[3][N] + SN[4][N] + SN[5][N] + SN[6][N] +
        SN[7][N] + SN[8][N] + SN[9][N]) % int(1e9);
    
    cout << ans;
}

---

   How to solve   

  계단 수 란, 인접한 모든 자리수의 차이가 1이 나는 숫자이다. 아래와 같은 수들은 모두 계단 수라고 할 수 있다.

 

• 456567898787
• 10101010
• 123456789

  또한, 0을 제외한 한 자리 수들(1 ~ 9)은 전부 계단 수로 분류한다.

 

  이 문제를 풀면서 분명 <Dynamic Programming (동적 계획)> 을 이용하기 위해 점화식을 세워서 하는 것인데 어떻게 세워야 할지 모르겠어서 머리를 많이 싸맸다. F[n] = F[n - 1] + An (An은 상수) 정도의 점화식이 나올 것이라 생각하고 상수 An의 규칙을 찾으려고 계속 애를 썼지만 결국 이렇게는 풀지 못 하였다. 상수 An에 대해서 어느정도 규칙성은 있을 것 같지만 이 규칙성은 찾기 어렵고 찾을 필요도 없는 규칙성일 것이란 생각이 든다.

 

  위 코드에서  vector<vector<unsigned long long>> SN;  처럼 SN 벡터를 선언하였다. 또한 그 바로 다음줄에 SN 벡터에게 10 * (N + 1) 개의 공간을 주고 값을 1로 초기화 하였다. N개의 열 공간이 아닌 N + 1개의 열 공간을 준 이유는 SN 벡터 열의 첫 인덱스를 1로 하고싶어서 그랬다! 그렇다면, SN 벡터가 의미하는 바는 무엇일까? 참, 벡터 이름을 SN라고 지은 이유는 그냥 문제가 계단 수 문제라 대충 Stair Number라고 줄여서 썼다 ;-) 이제 SN 벡터의 의미를 알아보자!

 

  우선 한 자릿수인 계단 수 집합은 { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } 이다. 그렇다면 이 집합과 두 자릿수인 계단 수 집합과의 연관성을 찾아보자. 위 집합의 원소들 뒤에 숫자 하나를 더 붙여서 두 자릿수를 만들어보자. 당연히 계단 수가 되게끔 만들어야겠다! 일반적으로 자기 자신보다 하나 큰 수, 하나 작은 수를 뒤에 붙인다면 두 자릿수 계단 수가 될 것 이란걸 알 수 있다. 예를 들어서 '2'뒤에 '1'이나 '3' 을 붙여서 두 자릿수 계단 수인 '21', '23'를 만들어낼 수 있다. 하지만 이 방식을 적용할 수 없는 숫자가 있다. 바로 '9'이다. '9'뒤에 '8'을 붙일 순 있지만 '9'보다 큰 한 자리 숫자는 없으므로 결국 '8'만 붙일 수 있다. 그렇게 두 자릿수인 계단수 집합은

 

{ 10 , 12 , 21 , 23 , 32 , 34 , 43 , 45 , 54 , 56 , 65 , 67 , 76 , 78 , 87 , 89 , 98 }

임을 알 수 있다. 응용하여 우리는 세 자릿수 계단수는 또 저 두 자릿수 계단수의 첫 번째 자릿수와 계단 수인 숫자를 뒤에 붙이면 만들어낼 수 있다는 것을 알 수 있다. 하지만 여기서 아까는 없었던 숫자인 '0'이 보인다. 이 숫자는 '9'와 같은 느낌이라고 생각하면 된다. '0'다음에 올 수 있는 숫자는 '0'보다 하나 큰 숫자인 '1'뿐이라는 것만 알면 되기 때문이다. 이제 SN 벡터의 의미를 설명할 수 있겠다.

 

SN [ k ][ A ] == A 자릿수를 가지는 계단 수 숫자중 첫째 자릿수 숫자가 k인 숫자들의 개수

  예를 들어서. SN[3][2]에 해당하는 숫자는 위 두 자릿수 계단수 집합을 참고하면 '23', '43'임을 알 수 있다. 따라서 SN[3][2] == 2 이다. 그렇다면 이를 점화식으로 표현해보면 SN[3][2] = SN[2][1] + SN[4][1] 이다. 이를 일반화하여 표현하면 SN[k][n] = SN[k - 1][n - 1] + SN[k + 1][n + 1] (단, 0 < k < 9) 이 된다. 예외를 둔 '0'과 '9'에 대한 점화식은 SN[0][n] = SN[1][n - 1] , SN[9][n] = SN[8][n - 1] 이 될 것 이다. 이에 해당하는 부분이 위 코드에서 16번째 ~ 27번째 line 이다.

 

  참고로 SN벡터의 공간들에 해당하는 값을 1로 초기화한 이유는, SN[1][1] ~ SN[9][1]의 값이 1이기 때문이다! SN[0][1]의 값은 0이므로 14번째 line에서 0으로 다시 초기화를 한 것을 볼 수 있다. 아래 표를 보고 다시한번 이해를 정리해보자.

 

[N자리 계단 수가 되면서 뒤에 붙는 수]

 

  또한, 문제에서 정답을 1,000,000,000으로 나눈 나머지를 출력하라고 했으므로 위 16번째 ~ 27번째 line에서 계속해서 점화식 우변의 값을 1,000,000,000으로 나눈 나머지를 좌변에 대입하였다. 문제에서 이렇게 하라고 하는 이유는 웬만하면 값이 너무 커져서 overflow가 발생하는 경우에 이렇게 하라고 한다. 이에 대해선 johoonday.tistory.com/17 를 참고해보자.

 

  답을 출력할 때엔 SN[0][N], SN[1][N], ... SN[9][N] 들을 더한 값을 1,000,000,000으로 나눈 나머지를 출력해야한다. SN[k][N] 의 의미가 N자리 계단 수중 첫째 자릿수가 k인 숫자들의 개수이기 때문이다!