[10844] 쉬운 계단 수

[10844] 쉬운 계단 수

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

코드

#include <iostream>

using namespace std;

/* 조건 */
#define DIVISOR 1000000000
#define MAX_N 101

/* 변수 */
int N, arr[MAX_N][10];
int result = 0;

int main() {
    /* 입력 */
    cin >> N;

    /* 풀이 */
    for(int i = 0; i < 10; i++) {
        arr[1][i] = 1;
    }

    for(int i = 2; i <= N; i++) {
        arr[i][0] = arr[i-1][1]%DIVISOR;
        for(int j = 1; j < 9; j++) {
            arr[i][j] = (arr[i-1][j-1]%DIVISOR) + (arr[i-1][j+1]%DIVISOR);
        }
        arr[i][9] = arr[i-1][8]%DIVISOR;
    }

    for(int i = 1; i < 10; i++) {
        result += arr[N][i]%DIVISOR;
        result %= DIVISOR;
    }

    /* 출력 */
    cout << result << '\n';
}

풀이과정

논리

문제에서 제시된 계단수를 구하는 것은 한자릿수부터 N자릿수까지 각 숫자별로(0부터 9까지)하나씩 구해보면 쉽게 구할 수 있다.
예를 들어, 3자리 숫자 중 4로 시작하는 계단수는 2자리 숫자 중 3과 5로 시작하는 계단수를 4 뒤에 붙인 43_과 45_가 된다.
위와 같이 한자릿수부터 각 숫자마다 더해가면 N자리숫자까지 구할 수 있을 것이다.

그리고, 숫자가 점점 커져 int의 범위를 넘어가기 때문에 정답을 1,000,000,000으로 나눈 나머지를 출력하도록 되어있으므로, 중간 중간 계산과정에 1,000,000,000을 나눠 나머지로 계산해주면 된다.

풀이

• 초기화
  먼저 첫 자리수는 계산할 수 없으므로 모두 1로 초기화 해주었다.

for(int i = 0; i < 10; i++) {
    arr[1][i] = 1;
}

• 계산
  한자리수는 채웠으니, 두자리수부터 N자리수까지 계산해준다.
  0과 9는 뒤에 1과 8만 올 수 있으므로 따로 계산해주고, 1부터 8까지는 1차이나는 숫자만큼 더해주었다.
  중간에 범위를 넘을 수 있으므로 무지성으로 모든 계산 과정에 나머지연산을 해주었다.

for(int i = 2; i <= N; i++) {
    arr[i][0] = arr[i-1][1]%DIVISOR;
    for(int j = 1; j < 9; j++) {
        arr[i][j] = (arr[i-1][j-1]%DIVISOR) + (arr[i-1][j+1]%DIVISOR);
    }
    arr[i][9] = arr[i-1][8]%DIVISOR;
}

• 정답 출력
  N자리 숫자까지 계산했으면, 첫번째 숫자로 0이 올 수는 없으므로 arr[N][1]부터 arr[N][9]까지 더해 출력해준다.
  이 때도 역시 범위를 초과할 수 있으므로 나머지 연산을 해주었다.

for(int i = 1; i < 10; i++) {
    result += arr[N][i]%DIVISOR;
    result %= DIVISOR;
}

출처

백준 [10844] 쉬운 계단 수
https://www.acmicpc.net/problem/10844