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

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

쉬운 계단 수는 예전에 스터디할 때도 풀었던 문제다..ㅎㅅㅎ 하지만 사실 완벽히 이해하지 못한게 사실이다...🙈

그래서 다시 풀었지 ㅎㅎ 아웅>_< 

 

우선 가장 처음으로.. ㅎㅅㅎ N이 2일때의 경우의 수를 써본다... 📝 

 

10, 21, 12, 32, 23, 43, 34, 54, 45, 65, 56, 76, 67, 87, 78, 98가 있다!

음...이 숫자들을 보면! 맨 마지막에 무엇이 끝나냐에 따라서 앞에 올 수 있는 경우의 수가 달라진다. (사실 prof. google 보고 알았다. 😬)

 

만약에! 마지막 자리가 3으로 끝난다고 가정해보자. 그러면 3 앞에 올 수 있는 숫자는 3 - 1, 3 + 1 인 2 와 4 이다. 그러면 N은 우리가 이미 3으로 지정을 해놓았고, 앞에 숫자들의 범위도 좁혔으니,  N - 1의 자리수를 가지면서 2와 4로 끝나는 숫자의 경우의 수를 우리는 가지고 오면 되는 것이다...이게 dp의 힘인가..?

 

이 과정에서 우리가 기억해야 하는 정보는 숫자의 길이와 끝자리 수이다. 이걸 이차원 배열로 표현해주면 된다 ㅎㅅㅎ 

 

사실 이렇게 쓰긴 썼는데 나도 내가 뭘 써 놓았는지 모르겠으니 역시 만능인 표를 만들어야겠다. 💻

 

다음은 i의 길이를 가지며  j로 끝나는 수의 경우의 수를 저장해놓은 배열이다!

 

예를 들어 arr[2][2]은 2의 길이를 가지며 2으로 끝나는 수의 가짓수다. 이 경우에는 12와 32가 있기 때문에 2가 저장돼 있다. 

 

각 칸마다 모든 경우의 수를 계산해줄 필요는 없다. 위에서 설명한 것처럼 2로 끝나는 경우에는 앞에 1과 3이 올 수 있다. 

그럼 수의 길이가 1이며 1과 3으로 끝날 때의 경우의 수를 앞에서 구해놨기 때문에 가져오면 된다!

그럼 arr[2][2]=arr[1][1]+arr[1][3] 이 된다! 

 

정리하면 각 칸은 arr[i][j]=arr[i-1][j-1]+ arr[i-1][j+1]이 된다 ㅎㅎ

 

표1. dp 배열

	0	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1	1
2	1	1	2	2	2	2	2	2	2	1

 

 

그리고 주의 해야할 점이 0으로 끝나는 수와 9로 끝나는 수는 앞에 올 수 있는 수가 제한적이다. 0으로 끝나는 수는 앞에 나보다 1 큰 숫자만 올 수 있고, 9로 끝나는 수는 나보다 1 작은 숫자만 올 수 있으니 N - 1 의 길이를 가지면서 0일 때는  +1 인 수와 9일 때는 -1 인 수가 왔을 때의 경우의 수를 가지고 오면 된다...

 

아래의 표를 보면 0 일 때에는 앞에 1만 올 수 있고, 9 일때에는 앞이 8만 올 수 있다! 

그러니 j가 0 일 때에는 arr[n][j+1] 이 될테고, j가 9일 때에는 arr[n][j+1]이 된다! 

 

표2. 길이가 N이며 j로 끝날때 계단수의 경우의 수 

0	1	2	3	4	5	6	7	8	9
10	21	12	23	34	45	56	67	78	89
		32	43	54	65	76	87	98
1	1	2	2	2	2	2	2	2	1

 

 

 

CODE!💻

#include <iostream>
#include <vector>

#define mod 1000000000
using namespace std;

int dp[101][10] = {
    0,
};
int main()
{
    int n;
    cin >> n;

    for (int i = 1; i < 10; i++) {
        dp[1][i] = 1;
    }

    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 10; j++) {
            if (j == 0)
                dp[i][0] = dp[i - 1][j + 1];
            else if (j == 9)
                dp[i][9] = dp[i - 1][j - 1];
            else
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];

            dp[i][j] %= mod;
        }
    }

    int result = 0;
    for (int i = 0; i < 10; i++) {
        result = (result + dp[n][i]) % mod;
    }
    cout << result << "\n";

    return 0;
}