백준10844 쉬운 계단 수

문제

풀이

#include <iostream>
using namespace std;

int main() {
    int input;
    cin >> input;
    int **arry;
    arry = new int *[input+1];
    int i = 0;
    int r, c;
    int result=0;

    for (i = 0; i <= input; i++)
        arry[i] = new int[10];

    for (i = 0; i < 10; i++) {
        arry[0][i] = 0;
        arry[1][i] = 1;
    }
    arry[1][0] = 0;

    for (i = 0; i <= input; i++)
        arry[i][0] = 0;

    if (input > 1) {

        for (i = 1; i <= 8; i++) {
            arry[2][i] = 2;
        }

        arry[2][9] = 1;

        for (r = 3; r <= input; r++) {
            for (c = 1; c <= 9; c++) {
                if (c - 1 == 0)
                    arry[r][c] = (arry[r - 2][1] + arry[r - 1][2])% 1000000000;
                else if (c + 1 == 10)
                    arry[r][c] =( arry[r - 1][8])% 1000000000;
                else
                    arry[r][c] = (arry[r - 1][c - 1] + arry[r - 1][c + 1])% 1000000000;
            }
        }
    }
    for (c = 0; c <= 9; c++)
        result = (result + arry[input][c])%1000000000;

    cout << result% 1000000000;

    return 0;
}

풀이방법

예를들어 생각해 보자
3자리수를 구하고자 할때
1ㅁㅁ
2ㅁㅁ
3ㅁㅁ
4ㅁㅁ
5ㅁㅁ
6ㅁㅁ
7ㅁㅁ
8ㅁㅁ
9ㅁㅁ
이 나올 수 있다.
이때 ㅁㅁ은
2자리 수에서 구할 수 있다.
즉 여기서 다이나믹 프로그래밍임을 알 수 있다.

다시 예제로 돌아와서.
3ㅁㅁ의 경우 32ㅁ or 34ㅁ이다.
1)즉 D[R][C] = D[R-1][C+1]+D[R-1][C-1]이다. (R은 자릿수, C는 0~9의 수)
2)첫째 자리가 1인 경우는 D[R-2][1]+D[R-1][2]
3)첫째 자리가 9인 경우는 D[R-1][8]만 된다.

1)즉 D[R][C] = D[R-1][C+1]+D[R-1][C-1]이다. (R은 자릿수, C는 0~9의 수)

2)첫째 자리가 1인 경우는 D[R-2][1]+D[R-1][2]

3)첫째 자리가 9인 경우는 D[R-1][8]만 된다.

문제를 풀며 1000000000으로 나누는것을 주의 하자. 생각보다 수가 엄청 커진다