10844번 : 쉬운 계단 수

Backjoon Online Judge 

"1005번 : 쉬운 계단 수" 문제입니다.

문제 링크 : https://www.acmicpc.net/problem/10844

쉬운 계단수에서 인접한 자리만을 쉽게 접근하기 위해 배열을 사용했습니다.

각 자리수 별로 계단 수를 구하고 ( 0자리 수 : -1, 1자리 수 : 1로 초기화)

더 큰 자리수는 이전 자리수에서 값을 더하는 DP 방식을 이용했습니다.

자리수가 0과 9일때는 인접한 자리수가 1개이고, 1~8 사이의 수일때는 인접한 자리수가 2개인 것을 활용했습니다.

아래는 코드 설명입니다.

 - 먼저 자리수가 0일때와 1일때 계단수를 초기화 했습니다.

 - 자리수가 2 이상 일때 첫자리 숫자에 따라 나올 수 있는 계단수를 DP를 통해 구했습니다. (1 차이 나는 이전 자리수를 더해주기만 하면 됩니다.)

 - 계단수의 크기가 1,000,000,000을 넘을 경우를 대비하여 덧셈 수행 마다 1,000,000,000으로 나눈 나머지를 저장하도록 했습니다.

(문제는 쉬웠지만 result 값을 0으로 초기화 해주지 않는 실수로 시간을 낭비했습니다. 실수 하지 않도록 체크)

코드는 C++로 작성하였습니다.

#include <iostream>
#define MAX 1000000000
 
using namespace std;
 
int main() {
    int N;
    long long int result = 0;
    long long int num[101][10] = { {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1} ,
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} };
    cin >> N;
    for (int i = 2; i <= N; i++) {
        for (int j = 0; j<10; j++) {
            if (j == 0) {
                num[i][j] = num[i - 1][1];
            }
            else if (j == 9) {
                num[i][j] = num[i - 1][8];
            }
            else {
                num[i][j] = (num[i - 1][j - 1] + num[i - 1][j + 1]) % MAX;
            }
        }
    }
    for (int i = 1; i < 10; i++) {
        result = (result + num[N][i]) % MAX;
    }
    cout << result << endl;
    return 0;
}