[Java] 백준 10844 : 쉬운 계단 수

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

10844번: 쉬운 계단 수

---

 

dp [][]의 이차원 배열을 사용해서 사용하면 된다.

dp [N][i]로 N은 몇 개짜리 계단인지를 의미하고,  i는 가장 맨 앞의 자릿수가 i일 때를 의미한다. 

이 내용을 그림으로 정리해봤다. 

dp [][]의 값 에는 해당 개수가 들어갈 예정이다. 

예를 들어, dp [2][3]= 2 이렇게.

 

그러면 어떻게 이 값을 구하냐가 문제인데 간단하다.

dp [2][3]일 때 만들 수 있는 계단은 3(N+1)과 3(N-1)이다. 즉, 34와 32이다.

하나의 계단이 추가되는 것이니까 dp [1][2]와 dp [1][4]의 값을 더해주면 된다. 

 

---

 

그런데, 0과 9의 경우에는 1~8과는 달리 0 옆에는 1, 9 옆에는 8 하나씩의 숫자만이 올 수 있다.

1,000,000,000로 나눈 나머지로 출력하라는 조건을 잘 보고 풀어야 한다..

깜빡하고 빼먹었다가 여러 번 틀렸다..ㅎㅎ

import java.util.*;

public class Main {
	
	static long[][] dp;
	static long mod = 1000000000;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N=sc.nextInt();
		dp = new long[N+1][10];
		
		/*
		 * N=> N개짜리 계단 
		 * if N=1
		 * 계단 : 1/2/3/4/5/6/7/8/9	=> 9개
		 * if N=2
		 * 계단 : 01/10,12/21,23/32,34/43,45/54,56/65,67/76,78/87,89/98	=>17개
		 */
				
		
		//N=1 경우의 수가 하나 
		for(int i=1;i<10;i++) {
			dp[1][i]=1;
		}
		
		//N>1
		for(int i=2;i<=N;i++) {
			//0~9까지 탐색
			 for(int j=0; j<10; j++) {
				 if(j==0) {
					 dp[i][j]=dp[i-1][1]%mod;
				 }else if(j==9) {
					 dp[i][j]=dp[i-1][8]%mod;
				 }else {
					 dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%mod;
				 }
			 }
		}
		
		System.out.println(Arrays.stream(dp[N]).sum()%mod);
		sc.close();
	}// main()
	
}// class Main