[백준] 쉬운 계단 수 - 10844

링크

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

문제

45656이란 수를 보자.

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

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자.
0으로 시작하는 수는 계단수가 아니다.

입력

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

출력

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

풀이

잘못된 생각(모든 경우의 수 파악하기)

N이 5인 경우, 10000 ~ 99999 사이의 값 중 계단 수를 세면 된다.
이럴 경우, 9만번의 반복문이 필요하게 된다.

N이 1 증가할 때 마다 10배의 반복문이 추가되므로
모든 경우의 수를 파악하는 방법은 옳지 않다.

패턴 파악하기

0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중
0과 9를 제외한 1~8의 값은 인접한 수가 2개이다.

즉, 1~8의 값은 두개의 숫자를 이용하여 만들 수 있고,
0과 9는 한 개의 숫자를 이용하여 만들 수 있다.

0과 2 뒤에는 1를 붙일 수 있고, 3과 5 뒤에는 4를 붙일 수 있다.
각 숫자 뒤에 올 수 있는 개수를 이용해 패턴을 만들 수 있다.

패턴 만들기

N이 1인 경우, 가능한 수는
1, 2, 3, 4, 5, 6, 7, 8, 9으로 총 9개다.
최하위 수가 0을 제외한 1~9 각 1개씩 사용되었다.

N이 2인 경우, 가능한 수는
10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98으로 총 17개다.
최하위 수가 0과 1, 9가 1개, 2~8이 각 2개씩 사용되었다.

이러한 패턴으로 표를 채우면 아래와 같다.

N에 따른 최하위에 0~9의 갯수가 몇개인지를 파악하여 결과를 산출했다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main {
    public static void main(String[] args) throws Exception {
        /**
         * 패턴
         * 0: 1로 생성
         * 1: 0과 1로 생성
         * 2: 1과 3으로 생성
         * ...
         * 8: 7과 9로 생성
         * 9: 8로 생성
         * 
         * 0123456789
         * 0111111111 -> 9
         * 1122222221 -> 17
         * 1334444432 -> 32
         */

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // input | N -> int
        int N = Integer.parseInt(br.readLine());

        // init | nums -> int[10]: 0~9      &     temp -> int[10]: 양옆을 더한 임시저장 값
        int[] nums  = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1};
        int[] temp = new int[10];

        // solve | 패턴 이용
        // 0~9 각 숫자의 양 옆을 더한 값을 temp에 채우고 nums를 temp로 치환
        int mod = 1000000000;
        for(;N>1; N--){
            for(int i=1; i<9; i++){
                temp[i] = (nums[i-1]%mod + nums[i+1]%mod)%mod;
            }
            temp[0] = nums[1];
            temp[9] = nums[8];
            System.arraycopy(temp, 0, nums, 0, 10);
        }

        // print
        Long answer = 0L;
        for(int num: nums)
            answer += num;
        
        System.out.println(answer%mod);
    }
}