아카이빙/BOJ

백준 10844번 - 쉬운 계단 수

셩님 2017. 7. 15. 19:15

백준 10844번 - 쉬운 계단 수

문제

  • 45656이란 수를 보자.

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

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

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


입력

  • 첫째 줄에 N이 주어진다.

  • N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.


출력

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


예제 입력

2

예제 출력

17


접근

  • Dynamic Programming으로 접근한다.

  • 첫 째 자리수에 올 수 있는 숫자는 1~9이다.

  • 만약 첫 째 자리수가 1이라면, 둘 째자리수는 0 또는 2가 올 수 있다.

  • 만약 첫 째 자리 수가 9라면, 둘 째자리수는 8만 올 수 있다.

  • 둘 째 자리 수가 0이라면, 셋 째자리수는 1만 올 수 있다.

  • 길이가 N인 계단 수는, N자리 수일 때 각 숫자 0~9가 올 수 있는 수의 총합이다.


점화식

  • : 숫자 n

  • : n자리 수에서, 숫자 i가 나올 수 있는 경우의 수

풀이

1) n이 3일때

D(n, Digit(i)) =
    i   0   1   2   3   4   5   6   7   8   9
    [1] 0   1   1   1   1   1   1   1   1   1
    [2] 1   1   2   2   2   2   2   2   2   1
    [3] 1   3   3   4   4   4   4   4   3   2       


C++ Code

#include <cstdio>
#include <vector>
using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    vector<vector<int>> d(n, vector<int>(10, 0));
    d[0] = { 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 };

    for (int i = 1; i < n; i++) {
        for (int digit = 0; digit < 10; digit++) {
            if (digit == 0) {
                d[i][digit] = d[i - 1][1];
            }
            else if (digit == 9) {
                d[i][digit] = d[i - 1][8];
            }
            else {
                d[i][digit] = (d[i - 1][digit - 1] + d[i - 1][digit + 1]) % 1000000000;
            }
        }
    }
    int sum = 0;
    for (int x : d[n - 1]) {
        sum = (sum + x) % 1000000000;
    }

    printf("%d\n", sum);

    return 0;
}
  • 출력시 정답을 1,000,000,000 으로 나눈 값을 출력해야 하기 때문에 더하기 연산 시 1,000,000,000으로 나눈 나머지 값을 대입시켰다.

  • int 자료형이 가질 수 있는 최대 양의 정수는 2^31-1 (2,147,483,647) 이다.

  • 따라서, 각 변수가 1,000,000,000으로 나눈 값을 가지므로, 두 값을 더하는 것 까지는 최대 범위를 초과하지 않는다.


'아카이빙 > BOJ' 카테고리의 다른 글

백준 2580번 - 스도쿠  (2) 2017.07.19
백준 9663번 - N Queen  (0) 2017.07.19
백준 2156번 - 포도주 시식  (2) 2017.07.15
백준 1912번 - 연속합  (1) 2017.07.15
백준 2293번 - 동전1  (5) 2017.07.15