[BOJ G5][#조합]1038번 감소하는 수

감소하는 수 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

30643

10093

7965

35.080%

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

예제 입력 1 복사

18

예제 출력 1 복사

42

예제 입력 2 복사

0

예제 출력 2 복사

0

예제 입력 3 복사

500000

예제 출력 3 복사

-1

 

📝 풀이

처음 시도는 브루탈포스로 풀어보았다. 

import java.io.*;

public class Main {
    static int result = -1;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        if (N <= 9) {
            System.out.println(N);
            return;
        }

        if (N > 1022){
            System.out.println(-1);
            return;
        }

        int cnt = 9;
        int i = 10;
        while (true) {
            if (solve(i)) {
                cnt++;
                if (cnt == N) {
                    result = i;
                    break;
                }
            }
            i++;
        }
        
        System.out.println(result);
    }
    
    public static boolean solve(int i) {
        char[] ch = String.valueOf(i).toCharArray();
        for (int j = 0; j < ch.length - 1; j++) {
            if (ch[j] <= ch[j + 1]) {
                return false;
            }
        }
        return true;
    }
}

 

조합 수의 최대는 1022개 즉 9876543210으로 이것을 제한해주고 원하는 만큼 돌렸는데

 

 

바로 시간초과 

그 이유는  987 다음의 감소하는 수는 4210으로 시작한다. 그렇기에 중간을 전부 계산해
시간 초과가 당연하게도 발생한 것이다.

 

그래서 모든 코드를 지우고 처음부터 다시 생각했다.

가장 높은 수	들어올 수 있는 것	조합
1	0	1, 10
2	1, 0	2, 20, 21, 210
3	2, 1, 0	3, 30, 31, 32, 310, 320, 321, 3210
4	3, 2, 1, 0	4, 40, 41, 42, 43, 410, 420, 421, 430, 431, 432, 4310, 4320, 4321

 

이 표를 통해 알 수 있는 것은 이것들이다.

• 가장 높은 수 기준으로 뒤의 수는 무조건 작은 수들만 온다.
• 가장 높은 수 기준으로 최대 자리 수가 정해진다. 

재귀를 통한 수의 조합으로 풀 수 있다는 것을 알았다. 

그리디 + DP 문제쯤??

        for (int i = 0; i < number % 10; i++) {
            generateNumbers(number * 10 + i, length + 1);
        }

이 부분은 수의 모든 조합을 만드는 식이다. 만약 length가 10을 넘는다면 종료한다.(10 이상의 감소수는 없기 때문)

 

📝 최종 코드

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

public class Main {
    static List<Long> decreasingNumbers = new ArrayList<>();

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

        if (N <= 9) {
            System.out.println(N);
            return;
        }

        if (N > 1022) {
            System.out.println(-1);
            return;
        }

        generateDecreasingNumbers();
        Collections.sort(decreasingNumbers);
        System.out.println(decreasingNumbers.get(N));
    }

    public static void generateDecreasingNumbers() {
        for (int i = 0; i <= 9; i++) {
            generateNumbers(i, 1);
        }
    }

    public static void generateNumbers(long number, int length) {
        if (length > 10) {
            return;
        }

        decreasingNumbers.add(number);
        for (int i = 0; i < number % 10; i++) {
            generateNumbers(number * 10 + i, length + 1);
        }
    }
}