백준 10844 (쉬운 계단 수)

문제

---

45656이란 수를 보자.

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

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

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

 

 

 

 

 

 

풀이

---

N이 1과 2일 때, 

N = 1 -> 1, 2, 3, 4, 5, 6, 7, 8, 9

N = 2 -> 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98

 

규칙을 찾아보면 N-1 의 수에서 -1, +1 해주는 것이다.

1차배열로는 이를 구현해내기 어렵기 때문에

2차배열로 뒷자리를 0~9 까지 저장을해서 갯수를 저장하는 방식으로 구한다.

 

예를들어

N = 1 일 때, 1은 N[1][1] 이다.

N = 2 일 때, 10, 12 는 N[2][1] = N[1][0] + N[1][2] 로 구할 수 있다.

 

이같은 방식으로 구하돼,

 

뒷자리가 0일 때, dp[N][0] = dp[N-1][1]

 

뒷자리가 9일 때, dp[N][9] = dp[N-1][8]

 

이렇게 두가지 경우만 제외하고는

 

dp[N][i] = dp[N][i-1] + dp[N][i+1] 

 

이 식으로 개수를 셀 수 있다.

 

문제에서 결과값을 1,000,000,000 으로 계속 나눈 나머지 값을 출력하라고 했으므로,

dp 에 저장 할때와 결과값을 1,000,000,000 으로 계속해서 나눠준다.

int 로 선언했을 경우 overflow 가 발생할 수 있으므로 long 으로 선언해서 문제를 푼다.

 

 

<코드>

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

public class Main {	
	
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		
	    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
	    
	    int n = Integer.parseInt(bufferedReader.readLine());
	    
	    long[][] dp = new long[n][10];
	    for(int i = 1 ; i < 10 ; i++) {
	    	dp[0][i] = 1;
	    }
	    
	    for(int i = 1; i < n ; i++) {
	    	dp[i][0] = dp[i-1][1];
	    	dp[i][9] = dp[i-1][8];
	    	for(int j = 1 ; j < 9 ; j++) {
	    		dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;
	    	}
	    }
	    
	    long sum = 0;
	    for(int i = 0; i < 10; i++) {
	    	sum += dp[n-1][i];
	    }
	    
	    System.out.println(sum % 1000000000);
	}

}