[백준(Baekjoon)][자바(java)] 10844 : 쉬운 계단 수 / 동적 계획법 1

 

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

10844번: 쉬운 계단 수

 

* 문제

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

 

* 풀이 방법

▶ 길이가 N이고, 0부터 시작하는 수는 없으므로 각각 0~9로 끝나는 수를 카운트 하기 위해 N*10의 dp배열 생성

  ( '~로 시작하는 수'를 구해봤는데 특별한 규칙을 발견하지 못했기 때문 )

    i : 자릿수 (길이)  ( 1 ~ n )

    j : 끝나는 숫자  ( 0 ~ 9 )

i / j	0	1	2	3	4	5	6	7	8	9	sum
1	0	1	1	1	1	1	1	1	1	1	9
2	1	1	2	2	2	2	2	2	2	1	17
3	1	3	3	4	4	4	4	4	3	2	32
4	3	4	7	7	8	8	8	7	6	3	61
5	4	10	11	15	15	16	15	14	10	6	116

 

▶  j가 0일 때, dp[i][j]는 dp[i-1][j+1]와 같다

▶  j가 9일 때, dp[i][j]는 dp[i-1][j-1]와 같다

▶  나머지 dp[i][j]는 dp[i-1][j-1] + dp[i-1][j+1] 와 같다

▶  길이가 N인 계단 수의 개수는 dp[N][0] ~ dp[N][9] 의 값을 모두 더한 값이 됨

 

import java.util.Scanner;

public class Main_09 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt(), i, j, m = 1000000000;
		long dp[][] = new long[n+1][10], sum = 0;
		
		for( i = 1; i <= 9; i++ ) 
			dp[1][i] = 1;		// dp[1][0] = 0;
		for( i = 2; i <= n; i++ ) {
//			for( j = 0; j <= 9; j++ ) {
//				if( j == 0 )		dp[i][j] = dp[i-1][j+1] % m;
//				else if( j == 9 )	dp[i][j] = dp[i-1][j-1] % m;
//				else dp[i][j] = ( dp[i-1][j-1] + dp[i-1][j+1] ) % m;
//			}
			dp[i][0] = dp[i-1][1] % m;
			dp[i][9] = dp[i-1][8] % m;
			for( j = 1; j <= 8; j++ )
				dp[i][j] = ( dp[i-1][j-1] + dp[i-1][j+1] ) % m;
		}

		for( i = 0; i <= 9; i++ )
			sum += dp[n][i] % m;
		
		System.out.println( sum % m );
		
		sc.close();
	}
}