BOJ 10844번 : 쉬운 계단 수

문제에서 언급한 계단수를 보면, 앞자리 숫자에 뒷자리 숫자가 영향을 받는다. 여기서부터 느껴지는 dp의 향연...... 차근차근 접근해 보자.

 

계단수의 길이가 1일때는 1부터 9까지 각 1개씩의 계단수를 가진다. 후에 편의를 위하여 0 또한 1개의 계단수를 가진다고 하자.

 

계단수의 길이가 2개 일때를 살펴보자. 계단수의 시작이 0이 될 수 없으므로 1부터 살펴보면, 1뒤에는 0과 2가 올것이다. 즉, 계단수의 길이가 1개 적을때의 값을 사용하게 된다. 2뒤에는 1,3이 올것이므로 동일하다.

다만, 시작하는 수가 9일 때는 뒤에 8만이 올 수 있다. 또한, 계산의 편의를 위해 0을 계산해 보면, 0으로 시작할 경우, 뒤에는 1만 올 수 있다.

 

이것을 표로 정리해보자.

다음과 같이 각 길이별/ 시작 숫자별로 연관관계를 맺게 된다.

1로 시작하는 2자리 계단수의 갯수는 0과 2로 시작하는 계단수 갯수의 합과 같게된다.

이렇게 되면, 대칭성을 띄게 되므로, 0~4의 계단수의 갯수와 9~5의 계단수의 갯수는 같게된다.

이때, 4와 5는 항상 같은 갯수의 계단수를 가지므로 아래 그림과 같이 축소 할 수 있다.

 

 

 

이제 n자리의 계단수 갯수는 sum(arr[0]~arr[4])*2 - arr[0]로 표현 할 수 있다. (0으로 시작하는 계단수는 빼주어야 한다.)

 

이제 dp과정에서 시작하는 수가 0일때와 4일때만 예외 처리를 해주고, 나머지는 반복문으로 해결이 가능하다. 또한, 1_000_000_000 으로 나눈 나머지 값이 요구 되므로, 연산시 모듈러를 해주어야 한다.

 

<소스코드>

#include <iostream>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define max 1000000000;
 
int main() {
    int n = 0;
    long long arr[101][5] = { 0, };
    long long res = 0;
    cin >> n;
    for (int i = 0; i < 5; i++) // 초기값 설정
        arr[0][i] = 1;
 
    for (int i = 1; i < n; i++) {
        arr[i][0] = (arr[i - 1][0] + arr[i - 1][1])%max; // 시작하는 수가 4 일때
        arr[i][4] = arr[i - 1][3]%max;                   // 시작하는 수가 0일때
        for (int j = 1; j < 4; j++)                      // 시작하는 나머지 수
            arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1])%max;
    }
    for (int i = 0; i < 5; i++)                          // 계단수 갯수 계산
        res = (res + arr[n - 1][i] * 2);
    
    cout<<(res-arr[n-1][4])%max;                         // 0으로 시작하는 계단수 제외
}
 

 

문제 :

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수