[백준 BOJ][DP] 10844 쉬운 계단 수

10844_쉬운 계단 수

 

링크

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

 

풀이

 

 

 

잠깐 생각해보면, n-1까지의 계단 수에 어떤 걸 더해서 n까지의 계단 수의 경우의 수를 구할 수 있을 것 같지만 조건이 부족합니다.

 

계단 수는 마지막 자리의 숫자로 그 다음 자리의 숫자가 뭐가 될지 결정됩니다.

다음 자리의 숫자가 3이 되려면 -1과 +1인 2, 4가 마지막 숫자여야 됩니다.

보통 이렇게 2가지를 갖지만 0과 9는 각각 1과 8가 마지막 자리일 때 가지게 됩니다.

이러한 특성 때문에 계단 수의 경우의 수를 구하기 위해서는 마지막 자리의 어떤 숫자가 몇 개씩 있는지 알아야만 합니다.

 

n은 1 <= n <= 100이니 101짜리 배열을 만들어야 하고 마지막 자리(0~9)까지 저장해줘야 되기 때문에 DP[101][10]를 만들 수 있겠네요.

 

맨 처음에는 DP[1][1] ~ DP[1][9]를 1로 초기화 해줍니다. 0으로 시작하는 숫자는 없다고 했기 때문입니다. 1로 초기화를 해줬다면 i=2부터 동적으로 경우의 수를 구할 수 있습니다.

 

i는 2부터 n까지, j는 0부터 9까지 for문을 돌려줍니다.

j가 0이라면, DP[i][j] = DP[i-1][j+1]            1에서만 올 수 있음.

j가 9라면, DP[i][j] = DP[i-1][j-1]               8에서만 올 수 있음.

다른 경우라면(else), DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]      양쪽에서 올 수 있음.

 

다 구한 후 DP[n][0] ~ DP[n][9]를 모두 더하면 총 경우의 수가 나옵니다.

 

주의할 점은 1,000,000,000으로 나눈 나머지로 출력해야 한다는 것입니다.

 

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

//10844_쉬운 계단 수 #include <iostream> #define mod 1000000000 using namespace std;   int DP[101][10];   int main() {     int n;     int i, j;     long long sum = 0;       for (i = 1; i <= 9; ++i) {        //1일 때 초기화 -> 2부터 동적으로 구할 수 있음         DP[1][i] = 1;     }       cin >> n;       for (i = 2; i <= n; ++i) {         for (j = 0; j <= 9; ++j) {             if (j == 0) DP[i][j] = DP[i - 1][j + 1];            //1에서만 올 수 있음             else if (j == 9) DP[i][j] = DP[i - 1][j - 1];        //8에서만 올 수 있음             else DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % mod;    //양쪽에서 올 수 있음         }     }       for (i = 0; i <= 9; ++i) sum += DP[n][i];            //총 경우의 수       cout << sum % mod << endl;       return 0; } Colored by Color Scripter

cs