10844번 쉬운 계단수

dp 풀이법

1) 일단 점하식을 만듦
2) 구현을 함.
3) 배열값 의 결과를 예상하면서, 입력으로 들어오는 값과 비교를 해보자.

다이나믹 프로그래밍

: 상태값이 2개가 있고, 그것을 배열에서 메모하면서
처리하는 것이 다이나믹 프로그래밍임.

• 상태값 : 길이 n / 인접한 자리의 차이 : 1

상태를 통해서 배열의 형태를 만들어보면
d[n][ ?? ]인데

점화식은 : 길이가 n이면서 인접합 자리의 차이가 1인 모든 경우의
계단수를 구하는 것임.

: 간단하게 생각하고 접근하면
d[n][l - 1] or d[n][l + 1]로 만들 수 있음.

그렇다면?
길이가 2인 경우의 모든 수는

idx : 2 1 / 2 1

길이가 2개인 계단 : 1 2 / 1 0
d[2][1] + d[1][0]
d[2][1] + d[1][2]

1번째 인덱스의 의미는 , 길이
2번째 인덱스의 의미는 , 마지막 자릿수의 카운팅

• 예제에서 나온 배열값인데,
  마지막 자릿수의 카운팅이면,
  길이가 2일 경우에는 [2][0] = 1? // [2][1] = 2??
  

점화식
d[idx][value] = d[idx -1][value - 1] + d[idx -1][value + 1]

• 그러면 길이가 1인 계단은 이렇게 표현이 가능함.
  d[1][1] = 1, d[1][2] = 1,d[1][3] = 1, ~~ d[1][9] = 1

// 추가적인 조건식이 필요함.

코드

#include <iostream>
using namespace std;

int main()
{
    // 점화식을 만들자. 
    // 상태값이 여기에 2개가 있음. 

    // 2개일 경우.
    // 12 10 21 23 32 34 43 
    // 45 56 54 65 67 76 78 89 87 98 
    // 하여튼 17개임.

    // 3개 일 경우에는 
    // 123 121  212  210 ~~ 
      
    //d[1][1] , d[1][2] ~~ d[1][9] -> 모두 다 1로 만들자.

    int n;
    cin >> n;

    long long d[101][10] = {0,};
    // 뒤에 0이 올수있음. but, 앞에 0이 올수는 없음.
    
    // 길이가 1인 숫자들에 해당하는 배열을 1로 설정함. 
    for(int i = 1; i < 10; ++i)
    {
        d[1][i] = 1;
    }
    // d[2][1] -> d[1][2] or d[1][0]
    // d[2][2] -> d[1][3] or d[1][1]

    for(int i = 2; i<= n; ++i)
    {
        for(int j = 0; j < 10; ++j)
        {
            // 점화식
              // d[idx][value] = d[idx - 1][value -1 ] 
             //+ d[idx][value + 1]
             //d[i][j] = 0;
             if(j >= 1)
                d[i][j] += d[i - 1][j - 1];
             if(j <= 8)   
                d[i][j] += d[i - 1][j + 1];
            d[i][j] %= 1000000000;
        }
    }
    long long res = 0;

    for(int i = 0; i < 10; ++i)
        res += d[n][i];

    res %= 1000000000;
    cout << res;

    //for(int i = 0; i < 3; ++i)
    //{
    //    for(int j = 0; j < 10; ++j)
    //    {
    //        cout << d[i][j] << " ";
    //    }
    //    cout << endl;
    //}
}