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

 

 

 

문제 출저

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

2688번: 줄어들지 않아

 

 

 

문제 풀이

숫자의 자릿수 n이 줄어듭니다. n일 때 줄어들지 않은 숫자의 갯수를 구해야 합니다. 테스트케이스 t의 갯수만큼 n이 주어집니다. 테스트케이스의 답을 내야합니다. 

 

 

dp로 문제를 풀었습니다. 

n의 범위는 1부터 65입니다. 줄어들지 않은 수는 전의 자릿수에서 연산을 통해서 구할 수 있습니다. 

0이 올 수 있는 경우는 그 전의 자릿수가 0인 경우

1이 올 수 있는 경우는 그 전의 자릿수가 0, 1인 경우

...

9가 올 수 있는 경우는 그 전의 자릿수가 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 입니다.

 

점화식을 세우면

dp[i][0] = dp[i-1][0]

dp[i][1] = dp[i-1][0] + dp[i-1][1]

...

dp[i][9] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][9]  입니다. 

 

long[] dp = new long[65][9] 를 배열을 선언한 후 dp를 통해 경우의 수를 전부 구합니다. 

n일 때 정답은 dp[n][0] + dp[n][1] + ... dp[n][9] 입니다. 

 

long[] answer = new long[65] 에 정답을 전부 저장합니다.

 

그 다음 테스트케이스 수만큼 n을 입력 받으면 answer 배열에서 해당 n을 찾아 정답을 출력합니다. 

 

65까지가면 숫자의 크기가 커지므로 int가 아닌 long을 사용합니다. 

 

 

소스 코드

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


/*
줄어들지 않아
https://www.acmicpc.net/problem/2688

0 1 2 3 4 5 6 7 8 9 자리가 있다.

0 -> 10
1 -> 9
...
9 -> 1


범위가 크기 때문에 long을 사용해야 한다. 

 */

public class Main {

  static StringBuilder sb = new StringBuilder();

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

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

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


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

    long[] answer = new long[65];
    for(int i = 1; i < 65; i++) {
      for(int j = 0; j <= 9; j++) {
        answer[i] += dp[i][j];
      }
    }


    while(t-->0) {
      int n = Integer.parseInt(br.readLine());
      sb.append(answer[n]).append("\n");
    }

    System.out.println(sb);




  }

}