Menu

Subscribe

[JAVA/백준] 동적 계획법 1: 쉬운 계단 수

HEESOO on Boj

👀 문제

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

👊 도전

1. 설계

  1. 이차원배열을 생성하여, dp[n][i]일때 길이가 n인 숫자 중 일의자리숫자가 i인 계단 수의 경우의 수를 저장하는 식으로 문제를 해결한다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

import java.util.Scanner;

/**
 * 
 * @author HEESOO
 *
 */
public class Main {
	public static void main(String[] args){
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		long[][] dp=new long[n+1][10];
		int mod=1000000000;
		long answer=0;
		
		for(int i=1;i<10;i++)
			dp[1][i]=1;
		
		for(int i=2;i<=n;i++){
			for(int j=0;j<10;j++){
				if(j==0)
					dp[i][j]=dp[i-1][j+1];
				else if(j==9)
					dp[i][j]=dp[i-1][j-1];
				else
					dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
				dp[i][j]%=mod;
			}
		}
		
		for(int i=0;i<10;i++)
			answer+=dp[n][i];
		answer%=mod;
		System.out.println(answer);
	}
}

3. 결과

실행결과 🤟 성공 🤟
예전에 DP문제인지 모르고 DFS로 풀었었는데 시간초과가 났었다.

4. 설명

  1. DP를 이용한다.
    • 이차원 배열 dp를 생성한다. dp[n][i]는 길이가 n인 숫자 중 일의자리숫자가 i인 계단 수의 갯수를 저장할 것이므로 dp의 크기는 dp[n+1][10]이다.
    • 길이가 n이고 일의자리가 i인 숫자는, 길이가 n-1이고 일의자리가 i-1 또는 i+1인 숫자 뒤에 i를 붙이면 계단 수가 완성된다.
    • 따라서 dp[n][i]=dp[n-1][i-1]+dp[n-1][i+1]이 된다.
    • 이때 i는 0~9까지이므로 i-1, i+1가 범위를 초과할 수 있으므로 그것에 대한 예외처리를 해준다.

👏 해결 완료!

참고