[BOJ] 10844. 쉬운 계단 수(DP 기초)

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

1. DP idx 정의

- dp[i][j]는 길이 i 계단에 j 로 끝나는 계단의 수

- 길이가 i 인 계단, 마지막이 j 로 끝나는 계단의 수  

2. 점화식 구하기

N = 1 : 01, 02, 03, 04, 05, 06, 07, 08, 09 (9개)

N = 1 :      01, 02, 03, 04, 05, 06, 07, 08, 09 

N = 2 : 10,      12, 23, 34, 45, 56, 67, 78, 89, 

               21, 32, 43, 54, 65, 76, 87, 98         (17개)

dp[2]에서 1로 끝나는 수는 dp[1]에서 0으로 끝날 경우와 1로 끝나는 경우가 있다. (dp[1][0] + dp[1][2] = 1)

dp[2]에서 2로 끝나는 수는 dp[1]에서 1로 끝날 경우와 3으로 끝나는 경우가 있다. (dp[1][1] + dp[1][3] = 2)

dp[2]에서 3으로 끝나는 수는 dp[1]에서 2로 끝날 경우와 4로 끝나는 경우가 있다. (dp[1][2] + dp[1][4] = 2)

...

dp[2]에서 8로 끝나는 수는 dp[1]에서 7로 끝날 경우와 9로 끝나는 경우가 있다. (dp[1][7] + dp[1][9] = 2)

dp[2]에서 9로 끝나는 수는 dp[1]에서 8로 끝나는 경우가 있다. (dp[1][8] = 1)

N = 1 :      01, 02, 03, 04, 05, 06, 07, 08, 09 

N = 2 : 10,      12, 23, 34, 45, 56, 67, 78, 89, 

               21, 32, 43, 54, 65, 76, 87, 98         (17개)

N = 3 : 210, 101, 212, 123 ...

121, 232, 323 ...

321, 432, 343...

 543 ...

으악.. 점화식 찾기 정말 어렵다ㅋㅋㅋㅋ

이렇게 DP문제를 많이 풀다 보면 다양한 점화식을 보게 될 테고..

이런 복잡하게 구해지는 점화식도 금방 캐취해낼 수 있겠지...?!

#. Code

#include <cstdio>
 
int dp[101][11];
 
int main(void)
{
    int n, i, j;
    long long res = 0;
    scanf("%d", &n);
 
    for (i = 1; i <= 9; i++)
        dp[1][i] = 1;
 
    for (i = 2; i <= n; i++) 
        for (j = 0; j <= 9; j++) 
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
 
    for (i = 0; i <= 9; i++) 
        res += dp[n][i];
 
    printf("%lld\n", res % 1000000000);
    return 0;
}

line 3) 최대 N은 100이고, 1의 자릿수는 0~9까지이므로 넉넉하게 dp[101][11]로 생성

line 8) 결과 변수를 처음에 int 자료형으로 하고 제출했을 때, 계속 틀렸습니다가 나와서 도대체 뭐가 문제인가 보다가 

    int 자료형을 long long 으로 바꿔주니까 성공하였다. 

    int 자료형 범위가 -2,147,483,648 ~ 2,147,483,647 이고, 1000000000 으로 나눈 나머지를 저장하면서

    int overflow가 그나마 해소되지 않을까 했는데, 아닌가보다.

    무튼.. 정답에 특정 수를 나누라는 뜻은 int overflow 방지용도라고도 하였으니, 

    왠만하면 이러한 경우에 long long 자료형을 써주는게 좋을듯 하다.

line 11) 직관적인 작은 문제의 해를 dp[][]에 저장

line 16) 점화식 적용 !! 

line 18) 길이가 n인 계단에 0~9로 끝나는 계단의 수를 누적하여 요구하는 답을 구해준다.