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

문제 설명

1. 계단 수란, 인접한 수의 차이가 1인 수이다. - 맨 앞이 0이되면 안됨.

2. 자릿수가 1이면 1,2,3,4,5,6,7,8,9 / 자릿수가 2이면 10,21,12,32,23,43,34,54,45,65,56,76,67,87,78,98,89 .....

3. 정답을 1000000000으로 나눈 나머지를 출력하면 된다.

풀이 과정

 1. DP로 문제를 풀었다( bottom-up으로 풀었음)

 2. 저기 문제 설명에서 자리수가 2이면에서 적어놓은 숫자들을 보면 왜 저렇게 적어 놓았는지 알 수 있을 것이다.

 3. 뒷자리 숫자가 0,1,2,3,4,5,6,7,8,9 이 순서대로 가면서 진행되고, 앞의 숫자들에서 법칙이 보일 것이다.

 4.

맨뒷자리	앞자리
0	1
1	0, 1
2	1, 3
.....	호롤로
8	7, 9
9	8

여기서 보면 알 수 있듯, 맨 뒷자리가 0, 9인 경우를 제외하면 모두 자기 전 DP의 자기보다 1큰수 + 자기보다 1작은수로 만들어진다.

 ex ) 2자리수의 0 <- 10        총 1개 (무조건 앞은 1이어야함)

       2자리수의 1 <-  01(맨앞이 0이라 안됨), 21   총 1개

       2자리수의 2 <- 32, 12   총 2개

       2자리수의 3 <- 43, 23   총 2개

       2자리수의 9 <- 89        총 1개 (무조건 앞은 8이어야함)

5. 이를 통해 세 가지 경우로 나누어 0인경우는 앞자리 1의갯수, 9인경우는 앞자리 8의갯수, 1~8인경우는 앞자리 앞뒤의 갯수의 합 이렇게 구하면 될것이다.

6. 그럼 처음에 n이 1인 경우의 값들을 정하고, bottom-up으로 구하자~

코드

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		long dp[][] = new long[n][10];	// n은 자릿수, 10은 0~9
		
		for(int i=1; i<=9; i++) dp[0][i] = 1;	// 숫자가 0일때는 0개이고 나머지는 1개씩

		for(int i=1; i<n; i++) {	// dp시작, 앞에서 가져옴
			dp[i][0] = dp[i-1][1]%1000000000;	// 0이면 무조건 앞자리 1
			dp[i][9] = dp[i-1][8]%1000000000;   // 9이면 무조건 앞자리 8
			for(int j=1; j<9; j++) dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])%1000000000; // 앞뒤꺼
		}

		long sum = 0;
		for(int j=0; j<=9; j++)
			sum += dp[n-1][j];		// 전체 개수는 당연히 앞의거를 포함하면서 진행하였으므로 맨 뒤의 개수이다.
		
		long ans = sum%1000000000;		// 참고로 1000000000으로 나눈걸 구해야 하는데, 위에서 long이 터져버리는걸 막기위해 계속 나눠가면서 진행했음.
		System.out.println(ans);
	}
}

매번 느끼는건데 DP는 종이에 풀이를 적기 전까지는 푸는 방법을 모르겠음...나만 그런가...? 다른 알고리즘은 익숙해지면 풀이가 생각나는데 DP는 직접 풀기 전까지는 감을 못잡는다.

아무래도 DP쪽 공부를 조금 더 해야할 것 같다.