다이나믹 프로그래밍_10844 : 쉬운 계단 수 JAVA

쉬운 계단 수 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

146709

47319

34551

30.635%

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

예제 입력 1 복사

1

예제 출력 1 복사

9

예제 입력 2 복사

2

예제 출력 2 복사

17

 

문제 설명을 보면 100자리 수까지 주어지니 기본 형식은 long 타입으로 간다.

이 문제의 키포인트는 인접한 모든 자릿수가 1씩 차이가 나는 것이다.

여기서 유의할 점은 두가지 이다.

 

1. N번째 자릿값이 0인 경우 : 다음 자릿값은 1밖에 올 수 없다.

2. N번째 자릿값이 9인 경 : 다음 자릿값은 8밖에 올 수 없다.

 

자리값은 0-9까지 넣을 수 있고, 자리수는 1부터 N까지 들어간다.

2차원 배열로 표현하였다.

 

long[][] arr = new [num+1][10]

 

배열은 0부터 시작하기 때문에 이해를 위해 num+1로 했다.

 

해당 문제는 다이나믹 프로그래밍 Buttom-up 방식으로 풀었다.

 

import java.io.*;

public class Main{
	final static long MOD = 1_000_000_000;
	public static void main(String[] args){
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.paresInt(br.readLine());
        long[][] arr = new long[num+1][10];
        for(int i=1;i<10;i++){
        	arr[1][i] = 1; // 자리수 1에 들어가는 자리값들의 경우의 수 (모두 1이다)
        }
        for(int i=2;i<=num;i++){
        	for(int j=0;j<10;j++){
            	if(j==0)
                	arr[i][j] = arr[i-1][1] % MOD; // 자리수가 두개 있고 오른쪽끝에 0이 들어갈 때 경우의 수는 자리수 하나있고 오른쪽끝에 1이 들어갈 때 경우의 수와 같다
                else if(j==9)
                	arr[i][j] = arr[i-1][8] % MOD; // 자리수가 두개 있고 오른쪽끝에 9가 들어갈 때 경우의 수는 자리수 하나있고 오른쪽끝에 8이 들어갈 때 경우의 수와 같다
                else
                	arr[i][j] = (arr[i-1][j-1] + arr[i-1][j+1]) % MOD; 나머지는 오른쪽끝에 j가 들어갈 때 경우의 수는 j-1, j+1 합친 경우의 수와 같다 
            }
        }
        long result = 0;
        for(int i=0;i<10;i++){
        	result+=arr[num][i]; // 자리값마다 경우의 수를 모두 더한다
        }
        System.out.println(result);
    }
}