백준 10844

후,, 점점 어려워 지고 있는 DP문제 ㅜㅜ 울고만 싶다,,

점화식 세우는거 왜케 어려울까 ㅜㅜ

혹시 팁이 있으시다면 알려주세요오~~~😭😭

 

▶백준 10844문제 - 쉬운 계단수

하나도 안쉬운 계단수,,,ㅜㅜ

 

▶풀이방법

- 2차원 배열 사용해야 함.

 

import java.io.*;
public 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));
		
		long mod = 1000000000;
		int num = Integer.parseInt(br.readLine());
		
		//int형 범위 넘을 수 있기 때문에 long형 사용해야함.
		long dp[][] = new long[num+1][10];
		
		//초기값 설정
		dp[1][0] = 0;
		for(int i = 1; i <= 9; i++) {
			dp[1][i] = 1;
		}
		
		for(int j = 2; j <= num; j ++) {
			dp[j][0] = dp[j-1][1]; //0으로 끝나는 수 개수
			for(int i = 1; i <= 8; i++ ) { //1~8로 끝나는 수 개수
				dp[j][i] = (dp[j-1][i-1] + dp[j-1][i+1]) % mod;
				}
			dp[j][9] = dp[j-1][8] % mod; //9로 끝나는 수 개수
		}
		
		//결과값
		long result = 0;
		for(int i = 0; i <= 9; i++) { //num의 0~9로 끝나는 모든 수의 합
			result += dp[num][i] % mod;
		}
		bw.write(String.valueOf(result % mod));
		bw.flush();
		bw.close();
		br.close();
	}
}

 

** 주의해야 할 점 **

-값이 점점 커지며 int형을 넘을 수 있기 때문에 long형으로 선언 해주어야 함.

- 계산 할때마다 mod = 1,000,000,000을 계속 나눠줄 것.