[백준/DP] 10844번 쉬운 계단 수 (JAVA)

문제

풀이

오답 코드

dp를 1차원 배열로 사용할 수 있는 점화식을 찾았다고 생각했는데, 아니었다.. 그래서 고민을 하다가 결국 구글링을 했다ㅠㅠ

import java.io.*;

public class Main {

    private static final int MAXIMUM = 100;
    private static final int MOD = 1000000000;

    private static int n;
    private static long[] dp = new long[MAXIMUM + 1];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        dp();
        bw.append(String.valueOf(dp[n]));

        br.close();
        bw.close();
    }

    private static void dp() {
        dp[1] = 9;
        for (int i = 2; i <= n; i++)
            dp[i] = (2 * dp[i - 1] - (i - 1)) % MOD;
    }
}

정답 코드

해결포인트는 dp를 2차원 배열로 선언하고, 마지막 자리의 숫자에 따라 경우의 수 값을 각각 저장하는 것이다. 이 방법을 읽자마자 풀이법을 곧장 적을 수 있었다.

1. 맨 끝자리가 0인 경우: i-1에서 1로 끝나는 수의 개수와 동일
2. 맨 끝자리가 9인 경우: i-1에서 8로 끝나는 수의 개수와 동일
3. 나머지 경우: i-1에서 j-1과 j+1로 끝나는 수의 개수의 합

import java.io.*;

public class Main {

    private static final int MAXIMUM = 100;
    private static final int MOD = 1000000000;
    private static final int NUMBERS = 10;

    private static int n;
    private static long[][] dp = new long[MAXIMUM + 1][NUMBERS];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        dp();
        bw.append(String.valueOf(sum(dp[n])));

        br.close();
        bw.close();
    }

    private static void dp() {
        for (int i = 1; i < NUMBERS; i++) dp[1][i] = 1;
        for (int i = 2; i <= n; i++)
            for (int j = 0; j < NUMBERS; 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]) % MOD;
    }

    private static long sum(long[] arr) {
        long sum = 0;
        for (long num : arr) sum = (sum + num) % MOD;
        return sum;
    }
}

참고

백준 10844번 쉬운 계단 수 :: 마이구미