[백준 2688] 줄어들지 않아 - JAVA

https://www.acmicpc.net/problem/2688

dp 문제

 

i번째 숫자에 어떤 num으로 도달했냐가 핵심이고, 0~i-1번째에 사용된 숫자는 유효하다면 기록할 필요가 없다.

 

수식

dp[i][num] = ∑_k=0^num-1 dp[i-1][k]

 

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

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int TC = Integer.parseInt(br.readLine());

    while (TC-- > 0) {
      int N = Integer.parseInt(br.readLine());

      long[][] dp = new long[N][10];

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

      for (int i = 1; i < N; i++) {
        for (int j = 0; j < 10; j++) {
          for (int k = 0; k <= j; k++) {
            dp[i][j] += dp[i - 1][k];
          }
        }
      }

      long ans = 0;

      for (int i = 0; i < 10; i++) {
        ans += dp[N - 1][i];
      }
      System.out.println(ans);
    }
  }
}