[백준 / 실버1] 11057 오르막 수 (Java)

문제 보기

사용한 것

• 숫자의 자릿수를 점차적으로 늘려 풀이하기 위한 DP

풀이 방법

• 2차원 dp배열을 사용한다.
  • 1차원의 인덱스는 자릿수
  • 2차원의 인덱스는 마지막 자리 숫자
  • 예를 들어 dp[3][1]은 "XX1"이 된다.
• 자릿수를 점점 늘려 for 문을 돌며
  • 2차원 for 문으로 다음 수의 마지막 자리 숫자 k가 가능한 경우를 모두 더해준다.
  • dp[i][k] += dp[i - 1][j];
• 문제에서 10007로 나눈 나머지를 출력하는 조건이 있으므로, 각 연산마다 고려한다.

코드

public class Main {

    private static final int TEN = 10;
    private static final int MOD = 10_007;

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // 2차원 DP 배열 초기화 ([자릿수][마지막 자리 숫자])
        int[][] dp = new int[n + 1][TEN];
        for (int i = 0; i < TEN; i++) {
            dp[1][i] = 1;
        }

        // DP
        for (int i = 2; i <= n; i++) {
            // 이전 수 마지막 자리 숫자 -> j, 다음 수 마지막 자리 숫자 -> k
            for (int j = 0; j < TEN; j++) {
                for (int k = j; k < TEN; k++) {
                    // 다음 수의 마지막 자리 숫자 k가 가능한 경우를 모두 더해줌
                    dp[i][k] = (dp[i][k] + dp[i - 1][j]) % MOD;
                }
            }
        }

        int answer = 0;
        for (int i = 0; i < TEN; i++) {
            answer = (answer + dp[n][i]) % MOD;
        }

        System.out.println(answer);
    }
}