[백준] 10844번 쉬운 계단 수 (Java)

subbni·2024년 5월 16일

DP 백준 코딩테스트

백준

목록 보기

20/24

10844번 문제

문제

풀이

길이가 N인 계단 수의 개수를 출력하면 되는 문제이다.

접근 방식

DP를 사용해 i(1<=i<=9)로 시작하는 길이가 N인 계단수의 개수를 구한다.

1,2,3,...9로 시작하는 길이가 N인 계단수의 개수를 모두 합하여 출력한다.

int[][] memo = int[10][N+1]

memo[i][n]에는 i로 시작하는, 길이가 n인 계단수의 개수를 저장한다.
이해가 쉽게 예를 들자면, memo[1][2]는 1로 시작하는 길이가 2인 계단 수의 개수이다. 10,12로 2개가 있으므로 memo[1][2]=2가 될 것이다.

0으로 시작하는 수는 계단수가 아니므로 memo[1~9][N]를 구하고 전부 합해주면, N 길이의 계단수의 개수를 모두 구할 수 있다.

제출 코드

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

public class Main {
    static int[][] memo;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        memo = new int[10][N+1]; // 0~9로 시작하는 길이가 N인 계단수의 개수
        for(int i=0; i<=9; i++) {
            memo[i][1] = 1;
        }
        long sum = 0;
        for(int i=1; i<=9; i++) {
            dp(i,N);
            sum += memo[i][N];
        }
        System.out.println(sum%1000000000);
    }

    static void dp(int num, int len) {
        if(len==0 || memo[num][len]!=0) return;
        if(num > 0) {
            dp(num-1,len-1);
            memo[num][len] = (memo[num][len]+memo[num-1][len-1])%1000000000;
        } 
        if(num < 9) {
            dp(num+1,len-1);
            memo[num][len] = (memo[num][len]+memo[num+1][len-1])%1000000000;
        }
    }
}