[10844] 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

---

 

🔎 해결 방법 

dp[1] = 9

dp[2] = 17

dp[3] = 32

dp[4] = 61 까지 찾고

점화식은 dp[i] = dp[i-1] * 2 - 1 이네! 하고 제출했는데 자꾸 틀렸다고 떠서 

질문들을 찾아보니....전부 dp를 2차원으로 선언했길래 굳이 2차원까지 써야 돼? 나는 1차원으로 해결하겠어...라며....1차원으로 하다가...

결국 2차원으로 선언했다.ㅎㅎ

 

이건 가지치기로 나타내서 보면 이해하기가 쉬운데, 아래의 그림을 보자.

 

우선 이 문제에서 dp는 dp[길이][최고 자리 수] 로 정의했다.

 

dp[4][1] = dp[3][0] + dp[3][2] 로 계산하면 되지만,

0으로 시작하는 숫자는 없기 때문에 dp[3][0]을 dp[2][1]로 고쳐서 더해주어야 한다.

 

즉, dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]로 계산하면 되지만,

j - 1이 0인 경우에는

dp[i][j] = dp[i - 2][1] + dp[i - 1][j + 1]로 계산하면 된다.

 

이와 비슷하게 j + 1이 10인 경우에는 

dp[i][j] = dp[i - 1][j - 1]로 계산해주면 된다.

그리고 출력할 떄는 dp[n][1], dp[n][2], ... dp[n][9] 를 다 더한 다음에 출력하면 되는데

dp의 변수형이 long long 타입이기 때문에 이 값을 다 더할 answer도 long long 타입으로 선언해야 하고,

answer += dp[n][i] 라고 하면 오류가 난다!

왜냐면 더하는 과정에서도 범위를 벗어나서 answer가 엄청나게 큰 값이 되어버릴 수 있기 때문...

그래서 answer = (answer + dp[n][i]) % 1000000000 이라고 해줘야 한다!

 

---

 

💡내 코드(C++) 

// [10844] 쉬운 계단 수
// https://www.acmicpc.net/problem/10844

#include <iostream>
using namespace std;

int main(void)
{
    int n, cnt = 0;
    long long dp[101][10], answer = 0;
    cin >> n;
    
    for(int i = 1 ; i < 10 ; i++) {
        dp[0][i] = 1;
        dp[1][i] = 1;
    }
    
    for(int i = 2 ; i <= n ; i++) {
        for(int j = 1 ; j < 10 ; j++) {
        
            if((j-1) == 0) {
                dp[i][j] = (dp[i-2][1] + dp[i-1][j+1]) % 1000000000;
                continue;
            }
            else if((j+1) == 10) {
                dp[i][j] = dp[i-1][j-1] % 1000000000;
                continue;
            }
            
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;
        }
    }
    
    for(int i = 1 ; i < 10 ; i++) {
        // 중요!! answer += dp[n][i] 라고 하면 오류!
        answer = (answer + dp[n][i]) % 1000000000;
    }

    cout << answer << endl;
}