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

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

10844번: 쉬운 계단 수

 

 

 

 

 

 

| 문제 해결방법

이 문제를 푸는데 약 두 시간이 걸렸다.

 

최대한 힌트를 참고하지 않고 풀어보려고 노력했더니 더 공부가 많이 되었다.

 

그리고 DP문제는 어떤 값을 메모제이션 할 것인지를 결정하는 것이 굉장히 중요한 것 같다. 

 

 

1. 첫 번째로 고려할 점

 

 

처음에는 dp배열에

계단수의 시작되는 수가 index인 위치에 각 경우의 수를 넣어주었다.

 

f(1) 인 경우,

0으로 시작되는 수만 제외하면

1부터 9까지 각각 자신의 수로 수를 만들 수 있다.

그래서 경우의 수는

 

 

f(1)

0 1 2 3 4 5 6 7 8 9

0 1 1 1 1 1 1 1 1 1

 

 

f(2) 인 경우,

위에 만들어진 숫자에 각각 +1 , -1 한 값을 붙여주었다.

0일때, 0으로 시작하는 수 제외 10 (1가지)

1일때, 12 - 10 (2가지)

2일때, 23 - 21 (2가지)

. . .

9일때, 10을 더해주는 경우 제외 98 (1가지)

 

 

f(2)

0 1 2 3 4 5 6 7 8 9

0 2 2 2 2 2 2 2 2 1

 

---

 

하지만 이렇게 나아가다 보니

규칙을 찾을 수 없었다.

 

그리고 구글링으로 작은 힌트를 얻고 다시 혼자 생각해보았다.

 

 

 

그 작은 힌트는 맨 뒤에 오는 수를 index로 보는 것이다.

 

예를 들면 문제와 같이

45656이란 수를 보자.

이 수의 맨 뒷자리 숫자는 6이다.

 

따라서 이 수가 만들어진 경우의 수는

dp[6]에 저장되어 있는 것이다.

 

이렇게 진행하면

dp[row][i] = dp[row-1][i-1] + dp[row-1][i+1] ( row = N , 0 ≤ i ≤ 9 )

이라는 점화식을 세울 수 있다.

 

 

f(2)

0 1 2 3 4 5 6 7 8 9

1 1 2 2 2 2 2 2 2 1

 

 

 

 

 

2. 두 번째로 고려할 점은 i가 0인 경우와 i가 9 인 경우이다.

두 경우는 각각 0 -1 ( 음수가 되므로 제외 ), 9 +1(10 으로 두 자리수가 되어 제외) 으로

 

if( i == 0 ) dp[row-1][i+1]

if( i == 9 ) dp[row-1][i-1]

 

 

만 더할 수 있게 하면 된다.

 

 

 

 

 

 

3. 마지막 고려사항은 데이터의 크기이다.

N은 1부터 100까지 가능한데

DP배열을 long으로 했다고 해도

 

DP배열을 채워주는 과정에서부터 작게 만들어주지 않으면( sum값에서만 1,000,000,000으로 나누면 )

결국, 음수가 나온다(long의 크기를 넘어서 오버플로우 발생)

 

위에서 이야기 했듯이

 

DP배열을 채워주는 과정에서부터 작게 만들어주는 것이 포인트! 

 

 

[JAVA] 해설 코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	// 26~30line 더할 때부터 나누어 주어야 long의 범위를 넘지 않는다
	static long div = 1000000000;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		long[][] dp = new long[n][10];
		
		dp[0][0] = 0;
		for(int i=1;i<10;i++) {
			dp[0][i] = 1; 
		}
		
		if(n>=2) {
			for(int row=1;row<n;row++) {
				for(int i=0;i<10;i++) {
					if(i==0) dp[row][i] = dp[row-1][i+1]%div;
					else if(i==9) dp[row][i] = dp[row-1][i-1]%div;
					else dp[row][i] =  dp[row-1][i+1]%div+ dp[row-1][i-1]%div;
				}
			}
		}

		long sum=0;
		for(int i=0;i<10;i++) {
			sum += dp[n-1][i];
		}
		sum %=div;
		System.out.println(sum);
		
		

	}

}