10844.쉬운계단수

문제

45656이란 수를 보자.

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

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

## 입력

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

## 출력

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	136447	43731	31781	30.389%

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

풀이

알고리즘 흐름

자리수가 100, 즉, 100째 자리 수까지 주어지는 문제이니 long 타입으로 문제를 풀어야한다. 이문제에서 가장 포인트는 인접한 모든수가 1씩 차이난다 는 것이다. 이를 바탕으로 문제를 풀어보자.

1) N번째 자리수의 자릿값이 0인경우 : 다음 자리수는 1만 가능하다.
2) N번째 자리수의 자릿값이 9인경우 : 다음 자리수는 8만 가능하다.

예를 들어, 10X 라고 할때 X에 들어갈수있는값은 1뿐 (101)이고, 19X라고 한다면 X에 들어갈수있는값은 8뿐(198) 인 것이다. 0과 9이외의 1~8까지는 앞뒤로 +1, -1을 가질수있다.

이러면 자릿값은 0~9를 가질수 있고, N개의 자릿값을 표현해야하므로 2차원배열이 필요하다.

Long[][] dp = new Long[n+1][10]; // dp [n자리수][자릿값]

 

이를 바탕으로 문제에 적용하여 보자. 점화식을 그대로 적용하여, 재귀를 사용하여 문제를 풀것이다. 재귀를 위해 자릿수을 표현할 digit , 자릿값을 표현할 val 변수를 사용한다.

*
 digit 는 자릿수, val은 자릿값을 의미함

 첫째 자리수는 각 val이 끝이기 때문에
 경우의 수는 1밖에 없다. 즉, dp[1]의 각 자릿값은
 1로 초기화 되어있어야한다.
*/

static long recur(int digit, int val) {        

    // 첫째 자리수에 도착한다면 더이상 탐색할 필요 없음
    if(digit == 1) {
        return dp[digit][val];
    }

    // 해당 자리수의 val값에 대해 탐색하지 않았을 경우 
    if(dp[digit][val] == null) {
        // val이 0일경우 이전 자리는 1밖에 못옴
        if(val == 0) {
            dp[digit][val] = recur(digit - 1 ,1);
        }
        // val이 9일경우 이전은 8밖에 못옴
        else if(val== 9) {
            dp[digit][val] = recur(digit - 1, 8);
        }
        // 그 외의 경우는 val-1과 val+1 값의 경우의 수를 합한 경우의 수가 됨
        else {
            dp[digit][val] = recur(digit - 1, val - 1) + recur(digit - 1, val + 1);
        }
    }
    return dp[digit][val];
}

코드

package 기초1.Day15.정해영;  

import java.util.Scanner;  

public class 쉬운계단수 {  

    static Long[][] dp;  
    static int n;  
    final static long MOD = 1_000_000_000;  

    public static void main(String[] args) {  

        Scanner sc = new Scanner(System.in);  

        n = sc.nextInt();  

        dp = new Long[n+1][10];  

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

        long result = 0;  

        for(int i=1; i<=9; i++){  
            result += recur(n,i);  
        }  

        System.out.println(result % MOD);  
        sc.close();
    }  

    /*  
     dist 는 자릿수, val은 자릿값을 의미함  

     첫째 자리수는 각 val이 끝이기 때문에  
     경우의 수는 1밖에 없다. 즉, dp[1]의 각 자릿값은  
     1로 초기화 되어있어야한다.  
    */  
    static long recur(int digit, int val) {  

        // 첫째 자리수에 도착한다면 더이상 탐색할 필요 없음  
        if(digit == 1) {  
            return dp[digit][val];  
        }  

        // 해당 자리수의 val값에 대해 탐색하지 않았을 경우  
        if(dp[digit][val] == null) {  
            // val이 0일경우 이전 자리는 1밖에 못옴  
            if(val == 0) {  
                dp[digit][val] = recur(digit - 1 ,1);  
            }  
            // val이 9일경우 이전은 8밖에 못옴  
            else if(val== 9) {  
                dp[digit][val] = recur(digit - 1, 8);  
            }  
            // 그 외의 경우는 val-1과 val+1 값의 경우의 수를 합한 경우의 수가 됨  
            else {  
                dp[digit][val] = recur(digit - 1, val - 1) + recur(digit - 1, val + 1);  
            }  
        }  
        return dp[digit][val] % MOD;  
    }  

}