[백준] 10844 쉬운 계단 수 - DP JAVA

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

10844번: 쉬운 계단 수

코드설명

DP 문제입니다.

 

dp[101][10] : 첫번째 배열은 자리수, 두번째 배열은 끝자리의 수일 때의 계단 수

 

예시로 들어보면

dp[1][3] 의 의미는 자리수가 1일때 끝자릿수가 3일때의 계단 수 의 개수를 의미합니다.

 

그렇다면 dp[1][0~9] 일떄의 값은 아래와 같습니다. 즉, 0 1 2 3 4 5 6 ... 일때는 당연히 한자릿수이므로 계단수가 본인 1개입니다.

dp[1][0] = 0

dp[1][1] = 1

dp[1][2] = 1

dp[1][3] = 1

dp[1][4] = 1

dp[1][5] = 1

dp[1][6] = 1

dp[1][7] = 1

dp[1][8] = 1

dp[1][9] = 1

 

dp[2][0~9] 일때의 값은 아래와 같습니다. 

dp[2][2]의 계단수는   12, 32 가 될 것입니다. 그렇기에 dp[1][2] + dp[1][3]  과 같습니다.

dp[2][0] = 1   => dp[1][0]

dp[2][1] = 2   => dp[1][0] + dp[1][2]

dp[2][2] = 2   => dp[1][1] + dp[1][3]

dp[2][3] = 2  => dp[1][2] + dp[1][4]

dp[2][4] = 2 

dp[2][5] = 2

dp[2][6] = 2

dp[2][7] = 2  => dp[i-1][6] + dp[i-1][8]

dp[2][8] = 2 

dp[2][9] = 1  

 

일반화해본다면,

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]; 입니다.

이떄 dp[i][0]과 dp[i][9] 는 각각 1과 8밖에 되지 않기에 dp[i-1][1], dp[i-1][8] 을 더해줘야합니다.

 

이렇게 N자리수까지 진행하면, 올바른 답을 구할 수 있습니다.

 

또한 문제에서 1,000,000,000 으로 나눠줘야하기에 각 연산마다 나머지 연산을 진행하고

마지막에 출력할때도 나머지 연산을 진행해줍니다.

 

코드

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

public class Main {
	public static int T, N, M;
	public static long answer = 0;
	public static int[] arr;
	public static long[][] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	dp = new long[101][10];
    	dp[1][0] = 0;
    	for(int j=1;j<=9;j++) {
    		dp[1][j] = 1; // 1 자릿수에서 1~9까지는 계단수의 개수는 1개밖에 안됩니다. 0 은 존재하지 않으므로 무시
    	}
    	
    	long mod = 1000000000;
    	for(int i=2;i<=N;i++) {
    		for(int j=1;j<=8;j++) {
    			dp[i][j] = ( dp[i-1][j-1] + dp[i-1][j+1] ) % mod;
    		}
    		dp[i][0] = dp[i-1][1] % mod;
    		dp[i][9] = dp[i-1][8] % mod;
    	}
    	
    	for(int j=0;j<=9;j++) {
    		answer += dp[N][j];
    	}
    	System.out.println(answer%mod);
    }
    
}