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

문제

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

참고 (1)

mygumi.tistory.com/260

백준 10844번 쉬운 계단 수 :: 마이구미

 

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

→ 길이가 N일 때, 마지막 수가 L일 경우의 계단 수

 

L = 0 → dp[N][L] = dp[N-1][L+1]

L = (1~8) → dp[N][L] = dp[N-1][L-1] + dp[N-1][L+1]

L = 9 → dp[N][L] = dp[N-1][L-1]

(0은 +1을 한 1만 허용되고, 9는 -1을 한 8만 적용되기 때문이다)

 

참고 (2)

위의 블로그가 이해 안된다면 영상으로 보는 것도 좋을 거 같다

1.75배속하면 적당한 속도가 된다ㅎ

www.youtube.com/watch?v=DkSVYYC_ANw

 

위 영상에서는 점화식이

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

임을 알려준다.

 

이 때,

dp[a][b] : a는 a번째 자리수, b는 a번째 자리수의 숫자이다.

→ dp[3][1] : 세자리 수, 3번째 자리 수가 1인 계단수의 개수

 

www.youtube.com/watch?v=nwqOSTa2c58

0번째, 9번째 처럼 예외 처리 해줘야 하는 경우에 대해서 설명해주심

 

코드

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

class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		long[][] dp = new long[N+1][10];
		
		for(int i=1; i<=9; i++) {
			dp[1][i] = 1;
		}
		
		for(int i=2; i<=N; i++) {
			dp[i][0] = dp[i-1][1];
			for(int j=1; j<9; j++) {
				dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])%1000000000;
			}
			dp[i][9] = dp[i-1][8]%1000000000;
		}
		
		long sum = 0;
		for(int i=0; i<10; i++) {
			sum+=dp[N][i];
		}
		bw.write(Long.toString(sum%1000000000)+"\n");
		bw.flush();
	}
}