[백준 2688번 / java] 줄어들지 않아

문제

2688번: 줄어들지 않아 (acmicpc.net)

풀이 1

dp+재귀호출 (시간 초과)

 

N은 숫자의 자릿수이다. 크기가 N인 배열 d를 만들고, d의 각 인덱스에 0부터 9까지 일일이 대입하여 d[x-1]와 d[x] 크기를 비교한다. 인덱스 0을 0~9로 미리 지정해두고 인덱스 1부터 비교한다.

 

1. d[0] 값을 0~9로 지정

2. 각각의 경우 dp함수 실행 (재귀)

   dp함수 :

     - 인덱스 x를 인자로 받아 dp[x-1]보다 큰 0~9에 대해 재귀 실행. 재귀 호출 시 인덱스 x+1을 넘겨준다.

     - 인덱스 x == N인 경우 dp[]가 끝까지 채워졌다는 뜻이므로 count++

3. count 출력

 

재귀 호출로 인해 시간 초과

코드 1

import java.util.*;
import java.io.*;

public class boj_2688 {
    static int[] d;
    static int count;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        int ans = 0;
        for (int i = 0; i < T; i++) {
            int N = Integer.parseInt(br.readLine());
            for(int j=0; j<=9; j++){
                d = new int[N];
                d[0] = j; //인덱스0값 설정
                dp(1);
            }
        }
        bw.write(count+" ");
        bw.close();
    }
    static void dp(int x){ //인덱스 x
        //x가 N-1일 때
        if(x == d.length) {
            count++;
            return;
        }
        //x가 N-1보다 작을 때
        for(int i=0; i<=9; i++){ //0~9 중
            if(d[x-1] <= i){ //이전 인덱스보다 크거나 같은 수가 있으면
                d[x] = i; //현재 인덱스에 그 수를 넣고
                dp(x+1); //인덱스 x+1 실행
            }
        }
    }
}

풀이 2

dp

규칙 찾기 -> 규칙을 통해 얻어진 값을 dp배열에 모두 저장한다 -> 저장된 값을 이용해 답을 구한다

규칙을 찾기 위해 먼저 가장 작은 문제부터 시작하여 풀이해나간다.

 

N=1부터 '줄어들지 않는 수'를 구해본다.

-> '줄어들지 않는 수'를 마지막 숫자가 0인 경우, 1인 경우.., 9인 경우로 나눈다.

-> N자리수의 마지막 숫자가 k인 경우의 개수 == N-1자리 수의 마지막 숫자가 0인 경우 ~ k인 경우 모든 합

-> 해당 값들을 모두 더하면 N자리수의 '줄어들지 않는 수'의 개수를 구할 수 있다.

 

1자리 수 :

0, 1, 2, ..., 9

(10가지)

 

2자리 수 : 

00

01, 11

02, 12, 22

03, 13, 23, 33

...

09, 19, ..., 99

(1+2+3+4+...+10 = 55가지)

 

3자리 수 :

000

001, 011, 111

002, 012, 022, 112, 222

003, 013, 023, 033, 113, 123, 133, 223, 233, 333

...

(1)+(2+1)+(3+2+1)+...+(9+8+...+1)

 

 

 

코드 2

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        long[][] dp = new long[65][10]; //64자리수, 마지막 숫자 0~9
        for(int i=0; i<=9; i++){
            dp[1][i] = 1; //1자리수는 모두 1
        }
        //dp값 채우기
        for(int i=2; i<=64; i++){
            for(int j=0; j<=9; j++){
                for(int k=0; k<=j; k++)
                    dp[i][j] += dp[i-1][k];
            }
        }
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<T; i++){
            long ans = 0;
            int N = Integer.parseInt(br.readLine());
            for(int j=0; j<=9; j++){
                ans += dp[N][j];
            }
            sb.append(ans).append("\n");
        }
        bw.write(sb.toString());
        bw.close();
    }
}