[백준 10844번 C++] 쉬운 계단 수

010844번: 쉬운 계단 수 (acmicpc.net)

10844번: 쉬운 계단 수

---

 

[문제 이해하기]

 

T(1) = 9

1 2 3 4 5 6 7 8 9 

 

T(2) = 17

1-> 12, 2-> 23, 21, 3-> 34, 32

12 23 34 45 56 67 78 89 90

21 32 43 54 65 76 87 98

 

T(3) = 2*T(2)

12-> 123 121, 23->232 234, 34->345 343, 90->901 909

21 -> 212 210 

 

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

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

이 접근 방식이 전혀 아니었다

[오르막 수] 문제와 비슷하게 접근해야 했다

2차원 배열을 이용하는 방법인데

하나씩 구해보면서 규칙을 찾아나가보면

 

길이가 1일 때: 9개 (1,2,3,4,5,6,7,8,9)

 

길이가 2일 때:

0으로 끝나면 0개 (0으로 시작할 수 없음)

1로 끝나면 1개 (21)

2로 끝나면 2개 (12, 32)

3으로 끝나면 2개 (23, 43)

..

9로 끝나면 1개 (89)

 

길이가 3일 때:

0으로 끝나면 1개 (010, 210)

1로 끝나면 3개 (101, 121, 321)

2로 끝나면 3개 (212, 232, 432)

3으로 끝나면 4개( 123, 323, 343, 543)

...

9로 끝나면 2개 (789, 989,

	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
3	1	3	3	4						2
4	3

=> arr[2][3] = arr[1][2] + arr[1][3]

arr[i][0] = arr[i-1][1]
arr[i][j]=arr[i-1][j-1]+ arr[i-1][j+1]
arr[i][9] = arr[i-1][8]

...

점화식 구하는 과정이 정말 어려웠다

0과 9의 예외점을 찾아 따로 점화식을 세워주는 게 쉽지 않았던 것 같다

 

그럼 이제 점화식이 세워졌으니 코드로 표현해봅시다..!!

---

코드로 잘 표현했다고 생각했는 데 제출하니까 틀림 

허허

문제의 코드는

#include <iostream>

using namespace std;

#define MAX 1000000000

int main()
{
    int arr[101][10];
    
    arr[0][0] = 0;
    for(int i=1; i<10; i++){
        arr[0][i] = 1;
    }
    
    for(int i=1; i<100; i++){
        for(int j=0; j<10; j++){
            if(j == 0) arr[i][j] = arr[i-1][1];
            else if(j==9) arr[i][j] = arr[i-1][8];
            else arr[i][j] = (arr[i-1][j-1]+ arr[i-1][j+1]) % MAX;
        }
    }
    
    int n;
    cin >> n;
    
    int sum=0;
    for(int i=0; i<10; i++){
        sum += arr[n-1][i];
    }
    
    cout << sum % MAX<< "\n";

    return 0;
}

위 해설 링크 코드랑 하나씩 비교해봤는 데 딱 하나가 누락된게 있었다

sum %= MAX;

...

sum 을 계속 더해줄 때도  MAX로 나눠줘야 했던 것....

그렇군요

그나저나 이 문제 이름 왜 쉬운 계단수? 

어려운 계단수로 수정 부탁드립니다

 

그렇게 내 최종 코드는

#include <iostream>

using namespace std;

#define MAX 1000000000

int main()
{
    int arr[100][10];
    
    arr[0][0] = 0;
    for(int i=1; i<10; i++){
        arr[0][i] = 1;
    }
    
    for(int i=1; i<100; i++){
        for(int j=0; j<10; j++){
            if(j == 0) arr[i][j] = arr[i-1][1] % MAX;
            else if(j == 9) arr[i][j] = arr[i-1][8] % MAX;
            else arr[i][j] = (arr[i-1][j-1]+ arr[i-1][j+1]) % MAX;
        }
    }
    
    int n;
    cin >> n;
    
    int sum=0;
    for(int i=0; i<10; i++){
        sum += arr[n-1][i];
        sum %= MAX;
    }
    
    cout << sum % MAX<< "\n";

    return 0;
}