[백준] JAVA 자바 : 오르막 수 (11057번)

---

오늘 근로하면서 오전 시간 내내 이것만 붙들고 있었는데...
진짜 한 3시간 정도 고민한 끝에 겨우겨우 점화식을 도출해서 풀 수 있었다...

난 아직 DP에 대해 전혀 알지 못하는 듯........

 

여튼 자릿수를 N으로 놓고 1부터 차근차근 올려보면

  dp[1] = 10; // 10

  dp[2] = 55; // 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1

  dp[3] = 220; // 55 + 45 + 36 + 28 + 21 + 15 + 10 + 6 + 3 + 1

  dp[4] = 715; // 220 + 165 + 120 + 84 + 56 + 35 + 20 + 10 + 4 + 1

  ...

이렇게 된다. 즉 직전 수에서 이전 배열의 자릿수에 있는 수 만큼을 뺀 값을 더하면 된다.
나도 글로 쓰기 어려워서 그냥 막 썼다. 자세한 건 코드를 보고 이해하시길 바랍니당~

 

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

public class UprisingNumber {

    static int MOD = 10007;

    public static int stoi(String str) {
        return Integer.parseInt(str);
    }

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

        int N = stoi(br.readLine());
        long[][] dp = new long[N+1][10];

        for (int i=0; i<=9; i++) {
            dp[1][i] = 1;
        }

        long sum = 10;
        for (int i=2; i<=N; i++) {
            dp[i][9] = sum;

            for(int j=8; j>=0; j--) {
                dp[i][j] = (dp[i][j+1] - dp[i-1][j+1]);
                sum += dp[i][j]%MOD;
            }
        }

        long res = sum % MOD;
        System.out.println(res < 0 ? res+MOD : res);
    }
}

로그인

 

 

 

작성일자: 2024-01-18