PS/BOJ

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

Jubil 2018. 6. 1. 21:16
반응형

10844_쉬운 계단 수

 

링크

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

 

풀이

 


 

 

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

 

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

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

보통 이렇게 2가지를 갖지만 09는 각각 18가 마지막 자리일 때 가지게 됩니다.

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

 

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

 

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

 

i2부터 n까지, j0부터 9까지 for문을 돌려줍니다.

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

j9라면, 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

 

 



반응형

'PS > BOJ' 카테고리의 다른 글

[백준 BOJ][DP] 2294 동전 2  (3) 2018.06.02
[백준 BOJ][DP] 2293 동전 1  (0) 2018.06.02
[백준 BOJ][DP] 1932 정수 삼각형  (0) 2018.06.01
[백준 BOJ][DP] 9095 1, 2, 3 더하기  (0) 2018.05.27
[백준 BOJ][DP] 11727 2xn 타일링 2  (5) 2018.05.27