[JAVA] 백준 10844번 【쉬운 계단 수】

---

먼저, 패턴을 찾기 위해 경우의 수를 살펴보자

 

 

0으로 시작하는 수도 경우의 수를 따져보았고, 결과를 출력할 때 더해주지만 않으면 문제가 없다.

 

메모이제이션을 위한, Dp[자릿수][시작하는수] 로 2차원 배열을 선언해준다.

---

0으로 시작하는 경우

---

3자리수로 만든 계단의 수를 살펴보면,

0으로 시작하는 수는 010 과 012 가 있다.

 

0을 때어놓고 보면, 10 과 12 임을 알 수 있고 0으로 시작하는 3자리 계단 수는 1로 시작하는 2자리 계단의 수임을 알 수 있다.

 

즉, 0으로 시작하는 N자리 계단 수는 1로 시작하는 N-1자리 계단의 수와 같다. 

 

Dp[N][0]=Dp[N-1][1]

 

 

---

9로 시작하는 경우

---

3자리수로 만든 계단의 수를 살펴보면,

 

9로 시작하는 수는 987 과 989가 있다.

 

9를 떼어놓고 보면, 87과 89임을 알 수 있고 9으로 시작하는 3자리 계단 수는 8로 시작하는 2자리 계단의 수임을 알 수 있다.

 

즉, 9으로 시작하는 N자리 계단 수는 8로 시작하는 N-1자리 계단의 수와 같다.

 

Dp[N][9]=Dp[N-1][8]

---

2~8로 시작하는 경우

---

3자리수로 만든 계단의 수를 살펴보면,

 

4로 시작하는 수는 432 434 454 456 이 있고

 

이는 2자리수의 3으로 시작하는 계단의 경우의 수 + 2자리수의 5로 시작하는 계단의 경우의 수가 됨을 알 수 있다.

 

즉, i(2~8)으로 시작하는 N자리 계단 수는 [i-1로 시작하는 N-1자리 계단의 수 더하기 i+1로 시작하는 N-1자리 계단의 수]와 같다.

 

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

---

결과

---

자릿수 N을 입력받으므로, Dp[N][0] ~ Dp[N][9] 까지 경우의 수를 모두 채우고, 

 

0으로 시작하는 계단수는 없다고 했기 때문에, 결과는 Dp[N][1] 부터 Dp[N][9] 까지 더해주면 된다!

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int mod = 1000000000;
		
		int[][] Dp = new int [N+1][10]; 
		
		for(int i=0;i<=9;i++) {
			Dp[1][i] = 1; //1자리 계단 수 
		}
		
		for(int i=2;i<=N;i++) {
			for(int j=0;j<=9;j++) {
				if(j==0) { //0으로 시작하는 계단 수
					Dp[i][j]=Dp[i-1][1]%mod;
				}
				else if(j==9) { //9로 시작하는 계단 수
					Dp[i][j]=Dp[i-1][8]%mod;
				}
				else { //2 ~ 8 로 시작하는 계단 수
					Dp[i][j]=(Dp[i-1][j-1]%mod+Dp[i-1][j+1]%mod)%mod;
				}
			}
		}
		int sum =0;
		for(int i=1;i<=9;i++) {// i는 1부터 시작! 0으로 시작하는 경우의 수 까지 더해주면 안됨!!
			sum+=Dp[N][i]; //N자리 1~9로 시작하는 경우의 수를 다 합하면 됨.
            			  
			sum%=mod;
		}
		System.out.println(sum%mod);
	}
}

 

오버플로우가 발생할 수 있으니 %mod를 꼼꼼히 넣어주는게 좋다.