백준 10844 쉬운 계단 수 JAVA (DP)

1. 문제

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

10844번: 쉬운 계단 수

 

2. 설명

6번 틀리고 맞은 문제 ㅋㅋㅋㅋㅋㅋ

첫 접근으로 점화식을 dp[n] = dp[n-1] * 2 - 1 로 세웠었는데,

백준 채점기가 틀렸다고 답해주셨다.

다르게 규칙찾는 방법으로, 공간을 늘려서 자릿수를 n까지 늘려가면서 구하는 방식으로 풀었다.

정답을 1,000,000,000으로 나눈 나머지를 출력하라고 하는 부분에서도 막힌게 있었는데,

그 전에는 sum+=dp[n-1][i]를 하고 전체 값을 mod로 나눴었다.

하지만 위 코드와 값 하나하나를 mod로 나눈 값이랑 결과가 다르기 때문에

아래 코드와 같이 코딩해야 한다.

 

3. 코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[][] dp = new int[101][10];
		int mod = 1000000000;
		
		for(int i=1; i<10; i++)
			dp[0][i] = 1; // 0으로 시작할 수 없음
		
		for(int i=1; i<n; i++) {
			for(int j=0; j<10; j++) {
				if(j==0)
					dp[i][j] = dp[i-1][j+1] % mod;
				else if(j==9)
					dp[i][j] = dp[i-1][j-1] % mod;
				else
					dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod;
			}
		}
		
		int sum = 0;
		for(int i=0; i<10; i++)
			sum = (sum + dp[n-1][i]) % mod;
		
		System.out.println(sum);
	}
}