[백준] 10844. 쉬운 계단 수

문제 링크

[백준] 10844. 쉬운 계단 수

풀이 과정

[백준] 1562. 계단수에서 0부터 9까지의 수가 한 번씩만 등장해야 하는 조건이 없는 문제입니다.

dp = new int[10][N + 1];

dp[i][j]는 첫 번째 수가 i로 시작하는 길이가 j인 모든 가능한 계단 수의 총 개수를 의미합니다.

static int go(int now, int length) {
    if (length == N) {
        return 1;
    }

    if (dp[now][length] != -1) {
        return dp[now][length];
    }

    int ret = 0;

    if (now - 1 >= 0) {
        ret += go(now - 1, length + 1);
    }

    if (now + 1 <= 9) {
        ret += go(now + 1, length + 1);
    }

    dp[now][length] = ret % MOD;

    return dp[now][length];
}

Top-down 방식의 go()는 재귀로 구현됩니다. 계단 수를 만들어가는 과정 중, 현재 숫자 now와 현재까지의 길이 length를 파라미터로 받습니다.

작동 과정은 다음과 같습니다.

• length가 N이면, 조건을 만족하는 계단 수를 하나 만든 것이므로, 1을 리턴한다.
• dp[now][length]를 이미 구한적이 있다면 그 값을 사용하도록 리턴한다.
• 구한적이 없다면, 계단 수 조건에 맞게 now 값과 length를 조정해 재귀를 호출해 그 개수를 얻어온다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N;
    static int[][] dp;
    static final int MOD = (int) 1e9;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        dp = new int[10][N + 1];
        int answer = 0;

        for (int i = 1; i <= 9; i++) {
            init();
            answer += go(i, 1);
            answer %= MOD;
        }

        System.out.println(answer);
    }

    static int go(int now, int length) {
        if (length == N) {
            return 1;
        }

        if (dp[now][length] != -1) {
            return dp[now][length];
        }

        int ret = 0;

        if (now - 1 >= 0) {
            ret += go(now - 1, length + 1);
        }

        if (now + 1 <= 9) {
            ret += go(now + 1, length + 1);
        }

        dp[now][length] = ret % MOD;

        return dp[now][length];
    }

    static void init() {
        for (int i = 0; i < 10; i++) {
            Arrays.fill(dp[i], -1);
        }
    }
}