DP - 10844. 쉬운 계단 수

문제

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

잠깐만

손으로 결과물들을 그려보세요 무엇인가 보일거에요.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int inputNum = Integer.parseInt(st.nextToken());
		
		int[] resultValues = new int[10];
		for (int n = 1; n < 10; n++) {
			resultValues[n] = 1;
		}

		for (int i = 2; i <= inputNum; i++) {
			int[] tempValues = new int[10];
			
			for (int n = 0; n < 10; n++) {
				if (n < 9 ) {
					tempValues[n] = resultValues[n+1];
				}
				if (n > 0) {
					tempValues[n] += resultValues[n-1];
				}
				tempValues[n] %= 1000000000;
			}
			
			resultValues = tempValues;
		}
		
		int resultValue = 0;
		for (int n = 0; n < 10; n++) {
			resultValue += resultValues[n];
			resultValue %= 1000000000;
		}
		
		System.out.print(resultValue);
	}
}

 

설명

세자리수 까지의 계단수를 그려보면 다음과 같습니다.

계단수 이기 때문에 특정 자릿수의 숫자가 n이라면, 그 다음 자릿수에는 n-1과 n+1만 올 수 있습니다.

예외 케이스가 있는데, 0과 9입니다.

0인 경우 다음 자리수에는 1만 가능(-1은 불가능하기 때문)하며, 9인 경우에는 8만 가능(10은 불가능하기 때문)합니다.

 

따라서 우리는 마지막 자릿수의 개수만 보면 되죠.

예를들어 3자리수의 1로 끝나는 계단수를 계산하기 위해선,

2자리수의 0으로 끝나는 계단수와 2로 끝나는 계단수의 개수만 계산하면 됩니다.

 

결과적으로 다음과 같이 표현할 수 있습니다.

이를 계산하면 되는데 함정은 1000000000으로 나눈 값입니다.

값을 저장할때도, 혹은 결과값을 모두 더할때도 % 계산을 해줘야합니다.

 

회고

최근에 풀어본 DP문제는 점화식 문제와 같습니다. 규칙을 찾고, 수식화 하여 로직으로 구현하라!