백준_10844 쉬운 계단 수(자바) / DP

시간 & 메모리 제한

문제

입력 & 출력

DP를 이용한 문제풀이

package com.Back;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Back_10844 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int Num = Integer.parseInt(br.readLine());
		long [][] dp = new long[Num+1][10] ;
		
		for (int i = 1; i < 10; i++) {
			dp[1][i]=1;
		}
		
		for (int i = 2; i <= Num; i++) {
			for (int j = 0; j < 10; j++) {
				if(j==0) dp[i][j] =dp[i-1][j+1]%1000000000;
				else if(j==9) dp[i][j] = dp[i-1][j-1]%1000000000;
				else dp[i][j] = (dp[i-1][j-1]+dp[i-1][j+1])%1000000000;
			}
		}
		
		long sum=0;
		for (int i = 0; i < 10; i++) {
			sum+=dp[Num][i];
		}
		System.out.println(sum %1000000000);
	}

}

- DP를 이용해서 문제를 풀었습니다.

 

- 문제의 접근 방법은

www.acmicpc.net/problem/11057

11057번: 오르막 수

이 문제와 비슷합니다.

 

- 점화식을 만들 때, 10의 일의자리는 더할수 밖에 없는 상황과 19의 일의자리는 뺄수 밖에 없는 상황만 고려하면 됩니다.

 

- 나머진 1을 더하고, 1을 빼는 방식으로 진행하면 문제를 풀 수 있습니다.

 

- 이 문제의 어려움을 겪었던 건, int가 담을 수 있는 값의 한계때문에 long으로 수정을 했습니다.