[10844번] 쉬운 계단 수(Dynamic Programming)

문제 출처 :

 

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. DP에 필요한 점화식 세우기

3. 예외 처리

Dynamic Programming을 이용하여 푸는 문제이다.

이 문제를 풀기위해서는 DP에 필요한 점화식을 세워야 하는데

길이가 1인 수는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9가 있다.

길이가 2인 수는 1의 자리수가 0일때는 10, 1의 자리수가 1일때는 01, 21, 1의 자리수가 2일때는 12, 32 ... 이 있다.

길이가 3인 수는 2의 자리수가 0일때 10x(x는 0~9이다.), 2의 자리수가 1일때 01x, 21x가 있다.

이렇게 계속해서 길이가 최대 100인 수까지의 점화식을 구해보면

DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]임을 알 수 있다.

동적 계획법(Dynamic Programming)이 생소하다면 이 점화식이 생소 할 지 모르지만, 직접 손으로 적어가며

아래의 표를 참조해보면 이해할 수 있다.

하지만 자연수이므로 01, 012같은 n번째 자리가 0인것은 마지막에 제외를 해 주어야 한다.

그리고 코드를 살펴보면 j가 0일때, j가 9일때가 있는데

0일때는 -1이 존재하지 않고, 9일때는 10이라는 것이 존재하지 않기에 이 과정에서는 예외처리를 해준다.

n번째 자리가 0인것을 제외하기 위해서는 아래 코드의 

sum을 구할 때, for문에서 1부터 9까지 돌려주면 된다.

즉 01, 0234819793 같은 n번째 자리가 0인것을 빼주면 된다.

DP[i][j]에 저장되는 값들은 다음과 같다.

소스 코드 : 

#include <stdio.h>
 
#define mod 1000000000
 
int main()
{
    int DP[101][10];
    int n,i,j;
    int sum = 0;    
 
    scanf("%d", &n);
 
    // 길이가 1로 이루어진 계단수는 모두 1이다.
    for (j = 0; j < 10; j++)
        DP[1][j] = 1;
 
    // 길이가 2이상인 계단수는 DP를 이용한다.
    for (i = 2; i <= n; i++)
    {
        for (j = 0; j < 10; j++)
        {
            // 만약 20, 30처럼 j가 0일때 -1은 없고 1이 가능하기에 
            if (j == 0)
                DP[i][j] = DP[i - 1][1] % mod;
 
            else if (j == 9)
                DP[i][j] = DP[i - 1][8] % mod;
 
            else
                DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1]) % mod;
        }
 
    }
 
    // 길이 n인 계단 수의 총 개수를 구한다.
    for (j = 1; j < 10; j++)
        sum = (sum + DP[n][j]) % mod;
    
    printf("%d", sum);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>