[백준 10844] 알고리즘 46일차 : 쉬운 계단 수

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

10844번: 쉬운 계단 수

동적계획법 C++

쉬운계단수 구하기

접근방법
1~8까지는 괜찮은데 0,9가 문제였다.

그래서 0,9 경우를 따로 계산하고

우선 기본적인 접근은 n번째 자리에 오는 0부터9까지의 숫자의 갯수를 저장하는 배열을 사용한다.

0의 개수는 이전 자리의 1의 개수

1~8(i)의 개수는 이전 자리의 i-1의 개수 + i+1의 개수

9의 개수는 이전 자리의 8의 개수

 

그리고 마지막에 n번째 자리에 오는 0~9의 개수를 모두 더한 값을 출력한다.

 

처음엔 마지막에 값을 더할때 나머지 계산을 안하고, 1~8의 경우를 저장할 때 i-1,i+1을 더한 후 나머지 계산을 안해서

오버플로우가 났었다.

그리고 배열은 1000000000로 나눈 값만 저장돼서 int여도 되지만

마지막에 이들을 더한 값을 출력하는 결과 값인 sum은 long이상 이어야 한다.

 

소스코드

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    int mod = 1000000000;
    int result[10][2];
    result[0][0] = 0;
    for(int i = 1 ; i <= 9 ; i++)
        result[i][0] = 1;
    
    for(int i = 1 ; i < n ; i++){
        for(int j = 0 ; j <= 9 ; j++){
            if(j==0)
                result[j][1] = result[j+1][0] % mod;
            else if(j==9)
                result[j][1] = result[j-1][0] % mod;
            else
                result[j][1] = (result[j-1][0] + result[j+1][0])%mod;
        }
        for(int j = 0 ; j <= 9 ; j++)
            result[j][0] = result[j][1];
    }
    long sum = 0;
    for(int i = 0 ; i <= 9 ; i++)
        sum += (result[i][0]%mod);
    cout << sum % mod;
    
    return 0;
}