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

 

📖 문제

 

📋 코드

import java.util.*;
public class Main {
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int MOD = 1000000000;
		int dp[][] = new int[101][10];
		
		for (int i = 1; i <= 9; i++) {
			dp[1][i] = 1;
		}
		
		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];
			dp[i][9] = dp[i-1][8];
		}
		
		int ans = 0;
		for (int i = 0; i <= 9; i++) {
			ans += dp[N][i] % MOD;
			ans %= MOD;
		}
		System.out.println(ans);
	}
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

 

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];
	dp[i][9] = dp[i-1][8];
}

 

dp[i][j] : i 길이의 수 마지막 부분이 j일 때 계단수

 

예를 들어 길이가 3이고 끝부분이 5일 때 계단수는 
길이가 2이고 4로 끝나는 계단수, 길이가 2이고 6으로 끝나는 계단수의 합입니다. 

그리고 길이가 i이고 끝자리가 0이거나 9인 경우에는
길이가 i-1이고 각각 끝자리가 1, 끝자리가 8인 경우만 가능하므로 예외로 반복문에서 빼서 계산해줍니다.

 

dp[i][j] = (dp[i-1][j-1]+dp[i-1][j+1])%MOD;

오버플로우가 발생할 수 있으니 dp를 구하는 과정에도 MOD를 해줘서 오버플로우를 방지해줍시다.

 

 

🔗 링크

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

10844번: 쉬운 계단 수