[백준]10844-쉬운 계단 수(Dynamic Programming)

정답률이 30퍼도 안되는 문제다.

근데 솔직히 정답률 더 높은 계단 오르기나 1로 만들기 문제보다 쉽게 느껴졌다. 왜지..?

요즘 동적 계획법 문제를 많이 풀어서 익숙해졌나?

아무튼..

 

이 문제는 의외로 간단하다.

중복을 생각할 필요가 없다. 대신 예외를 생각해야한다.

1에서 파생되는 수는 10, 12가 있다.

2에서는 21, 23이 있다.

등등..

그럼 두 자리 숫자로 넘어가보자.

10에서 파생되는 수는? 101뿐이다.

89에서 파생되는 수는? 898뿐이다.

나머지는 모두 끝 자리 숫자에 1을 빼고 더하는 두 가지 경우가 나온다.

복잡하게 생각하지 말고 맨 끝자리만 보면 된다.

 

길이 N인 계단 수 중에서 끝자리가 0인 수의 개수는? 길이 N - 1인 계단 수 중에서 끝자리가 1인 수의 개수와 같다.

끝자리가 0인 계단 수를 만들 수 있는 수는 끝자리가 1인 계단 수밖에 없기 때문이다.

 

길이 N인 계단 수 중에서 끝자리가 9인 수의 개수는? 길이 N - 1인 계단 수 중에서 끝자리가 8인 수의 개수와 같다.

끝자리가 9인 계단 수를 만들 수 있는 수는 끝자리가 8인 계단 수 밖에 없기 때문이다.

 

그러면 길이 N인 끝자리가 j(범위 1~8)인 계단 수의 개수는? 끝자리가 j - 1, j + 1인 길이 N - 1계단 수의 합과 같다.

 

표로 정리해보자.

0	1	2	3	4	5	6	7	8	9
0	1	1	1	1	1	1	1	1	1
1(1)	1(0 + 1)	2(1 + 1)	2(1 + 1)	2(1 + 1)	2(1 + 1)	2(1 + 1)	2(1 + 1)	2(1 + 1)	1(1)
n[i - 1][0]	n[i - 1][1]	n[i - 1][2]	n[i - 1][3]	n[i - 1][4]	n[i - 1][5]	n[i - 1][6]	n[i - 1][7]	n[i - 1][8]	n[i - 1][9]
n[i][0]= n[i - 1][1]	n[i][1]= n[i - 1][0] + n[i - 1][2]	n[i][2]= n[i - 1][1] + n[i - 1][4]	n[i][3]= n[i - 1][2] + n[i - 1][4]	n[i][4]= n[i - 1][3] + n[i - 1][5]	n[i][5]= n[i - 1][4] + n[i - 1][6]	n[i][6]= n[i - 1][5] + n[i - 1][7]	n[i][7]= n[i - 1][6] + n[i - 1][8]	n[i][8]= n[i - 1][7] + n[i - 1][9]	n[i][9]= n[i - 1][8]

위와 같이 정리된다.

 

이를 코드로 정리하면

//#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
 
long long stair(int N);
 
int main() {
    int N;
    scanf("%d", &N);
    printf("%d\n", stair(N));
}
 
long long stair(int N) {
    int** ary = new int* [N+1];
    for (int i = 1; i <= N; i++)
        ary[i] = new int[10]{ 0, };
    for (int i = 1; i < 10; i++)
        ary[1][i] = 1;
 
    for (int i = 2; i <= N; i++) {
        ary[i][0] = ary[i - 1][1];
        ary[i][9] = ary[i - 1][8];
        for (int j = 1; j < 9; j++)
            ary[i][j] = (ary[i - 1][j - 1] + ary[i - 1][j + 1]) % 1000000000;
    }
    long long value = 0;
    for (int i = 0; i < 10; i++)
        value += ary[N][i];
    return value % 1000000000;
}