[BOJ] 1038. 감소하는 수

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

접근 방법

오랜만에 동적 프로그래밍 문제를 풀려니 어려웠었다..

처음 접근 방법은

숫자들을 증가시키면서 이 숫자가 감소하는 숫자인지 확인해보았다.

당연히 이 방법은 시간초과가 났다...

그래서 구글링을 해서 찾아본 결과

---

• {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}의 각 부분 집합을 이용해 만들 수 있는 감소하는 수는 각각 1개이다.
• 예를 들어, {1, 4, 7, 9} 라는 부분 집합을 이용해서 만들 수 있는 감소하는 수는 9741 단 하나이다.

이것이 힌트이다.

그렇다면 이제 어떻게 하면 감소하는 수를 찾을 것 인가? 가 남았다.

---

먼저 0~9까지의 숫자를 받아서

[감소하는 수] + [감소하는 수의 맨 뒷자리의 수보다 작은 수] 를 하게 되는 방법이다.

static void getDecreaseNumber(long num){
        long val = num % 10, cur = num * 10;
        for(int i = 0; i < val; i++){
            ans[cnt++] = cur + i;
            getDecreaseNumber(cur + i);
        }
    }

Need Know

1. DP

전체 코드 ( Java )

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N ;
    static int cnt = 0;
    static long[] ans = new long[1023];
    public static void main(String[] args) throws IOException {
        set();
        solve();
        bw.flush();
        bw.close();
        br.close();
    }

    static void set() throws IOException {
        N = Integer.parseInt(br.readLine());
    }

    static void solve() throws IOException {

        for(int i=0; i<10; i++){
            ans[cnt++] = i;
            getDecreaseNumber(i);
        }
        Arrays.sort(ans);
        if(N < cnt){
            bw.write(ans[N] +"");
        }else{
            bw.write(-1 +"");
        }
    }
    static void getDecreaseNumber(long num){
        long val = num % 10, cur = num * 10;
        for(int i = 0; i < val; i++){
            ans[cnt++] = cur + i;
            getDecreaseNumber(cur + i);
        }
    }

}