[백준,BOJ 10844] 쉬운 계단 (JAVA 구현)

-내 생각

  문제 이름은 쉬운 계단 수있은데 쉽지가 않다 ㅋㅋㅋㅋㅋㅋ 당연히 못 풀었고 다른 분들의 글을 참고했다.

 

-해법

  이 문제의 경우 dp[N][10]의 2차원 배열을 사용해야 한다. N은 숫자의 자릿수를 의미하며 10은 0~9의 끝자리를 의미한다. 다른 분들의 경우 0~9를 끝자리로 두지 않고 푼 경우도 봤는데, 끝자리로 두고 푼 분들이 더 많았다.  우선 초기 dp배열은 N이 1일 경우이다. 0~9까지 이지만, 0으로 시작하는 경우는 존재하지 않는다고 언급했기 때문에 0을 제외한 1~9는 1자리 수이므로 모두 1로 채워준다. (값들은 각 숫자가 끝자리에 오는 경우의 수를 의미한다.)

 

  이후 N이 2일 경우, 0이 끝자리에 오는 경우는 앞자리가 될 수 있는 수들은 0 -1 , 0 +1이 된다. 그러나 0 -1의 경우는 -1이 되므로 넘어가고, 1만이 올 수 있으므로 10밖에 존재하지 않는다. 다음 끝자리가 1일 때 앞자리가 될 수 있는 경우는 1 -1 , 1+1로 0과 2인데, 0 역시 넘어가고 21밖에 존재하지 않는다. 다음 끝자리가 2일 때 앞자리가 될 수 있는 경우는 2-1, 2+1로 1과 3이므로 12와 32가 될 수 있다. 이런 식으로 마지막 끝자리가 9일 경우 앞자리는 9 -1인 89밖에 존재하지 않는다.

 

  마지막 예시로 N이 3일 경우, 0이 끝자리에 오는 경우 앞 자리는 위의 경우에서 봤듯 10 한 가지밖에 존재하지 않고 3리 수 이므로 기준을 0에서 1로 옮겨 다시 1로 끝나는 경우 앞자리에 올 수 있는 경우는 21밖에 없으므로 최종적으로 210 한 가지가 존재하는 것이다. 또 1로 끝나는 경우는 01, 21이 가능하며 01의 경우는 101, 21의 경우는 121, 321이 존재한다. 그러므로 3가지의 경우가 존재하게 된다. 즉, 각각의 끝나는 자릿수가 가질 수 있는 앞자리의 후보들이 이전 자릿수의 경우를 몇 개 가지고 있는지만 알면 된다. (더 쉽게 이야기해보자면, N이 3일 때 1로 끝나는 경우 앞자리는 0과 2가 가능하며, 3 자리 수 이므로 N이 2일 때 구해놓은 0과 2로 끝나는 경우의 수를 더해주면 되는 것이다.) 

 

  dp[n][i] = dp [n-1][i-1] + dp [n-1][i+1]이 성립하면 되는 것이다.

 

  이와같은 방식으로 N이 4일 경우, 끝 자리가 1일 때, 앞자리는 0 또는 2며 앞서 채워주어야 할 3자리는 N이 3일 때 구해놓은 끝 자리가 0일 때의 경우의 수와 2일 때의 경우의 수를 합해주면 알 수 있다.

 

  마지막으로 각각의 결과를 나머지로 저장 해 두었는데, 마지막에도 나머지를 해주는 이유는 최종 결과를 모두 더해주는 과정에서 1,000,000,000의 범위를 벗어났을 경우를 위해서다. 

 

import java.util.*;

public class Main {
	static int n;
	
	static long dp[][];
	
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		n=sc.nextInt();
		dp = new long [n+1][10];
		
		
		for(int i=1;i<=9;i++) { // dp배열 초기상태
			dp[1][i] = 1;
		}
		
		for(int i=2;i<=n;i++) { // 2인 경우부터 N까지 반복
			for(int j=0;j<10;j++) {
				if(j==0) dp[i][j] = (dp[i-1][j+1]) % 1000000000; // 끝자리가 0일 경우는 1일 때만 고려
				else if(j==9) dp[i][j] = dp[i-1][j-1] % 1000000000 ; // 끝자리가 9일 경우는 8일 때만 고려
				else dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])% 1000000000; // 나머지는 -1, +1 모두 고려
			}
		}
		long sum=0;
		for(int i=0;i<10;i++) {
			sum +=dp[n][i];
			
		}
		
		System.out.println(sum % 1000000000);
		
		
		
	}
	
}