쏚쏚스포이드

백준 감소하는 수(줄어드는 수)

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

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

접근 방식

최초엔 n까지 범위의 수를 생각했는데, 잘못 생각한 것이였고, 앞자리부터 점점 감소하는 수의 모든 경우의 수 중 몇번째인지 n으로 입력받아 찾는 문제

구현 방법

• 감소하는 수에 대해 모든 조합을 찾은 후 정렬해 수행
• 이 때 최대 수의 범위까지 1씩 더해가며 찾는 것이 아닌, 값이 들어갈 수 있는 범위에 대해서만 찾기

⇒

• 9876543210 까지가 최대 수
• 재귀에서 자릿수(depth)를 받아서 depth 범위만큼 foreach돈다.
• 기본적으로 for문 돌 때 자기보다 낮은 수에 대해서만 수행
• 재귀 안에서 count가 같으면 return - count는 static으로 갖고있기에 종료가능
• for문이 다 돌면 재귀호출 시행

풀이

package Baekjoon.gold;

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class p1174 {

    static Stack<Long> st = new Stack<>();
    static ArrayList<Long> al = new ArrayList<>();

    static int count = 0;
    static int n;
    static StringBuilder sb = new StringBuilder();

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

        n = Integer.parseInt(br.readLine());

        /*
         0, 1, 2, 3, 4, 5, 6, 7, 8, 9
         10 | 20, 21 | 30, 31, 32 | 40, 41, 42, 43 | 50, 51, 52, 53, 54 |
         60, 61, 62, 63, 64, 65 | 70, 71, 72, 73, 74, 75, 76 |
         80, 81, 82, 83, 84, 85, 86, 87 | 90, 91, 92, 93, 94, 95, 96, 97, 98 |
         210 |320, 321, 310 | 410, 420, 421, 430, 431, 432
         */

        //9 -> 8 7 6 5 4 3 2 1 0
        //8 -> 7 6 5 4 3 2 1 0
        //7 -> 6 5 4 3 2 1 0
        //6 -> 5 4 3 2 1 0
        //5 -> 4 3 2 1 0
        //4 -> 3 2 1 0
        //3 -> 2 1 0
        //2 -> 1 0
        //1 -> 0

        // 10 20 21 30 31 32
        //9876543210 까지가 최대 수
        //재귀에서 자릿수(depth)를 받아서 depth 범위만큼 foreach돈다.
        //기본적으로 for문 돌 때 자기보다 낮은 수에 대해서만 수행
        //재귀 안에서 count가 같으면 return - count는 static으로 갖고있기에 종료가능
        //for문이 다 돌면 재귀호출 시행

        if(n <= 10){
            System.out.println(n-1);
            return;
        }
        recur(10);
        List<Long> list = al.stream().sorted().collect(Collectors.toList());

        long result = -1;
        if(list.size() >= n){
            result = list.get(n-1);
        }

        System.out.println(result);
    }

    private static void recur(long nowNum){
        for(long i = 0; i < nowNum; i++){
            count++;
            st.push(i);
            st.forEach(sb::append);
            al.add(Long.valueOf(sb.toString()));
            sb.setLength(0);
            recur(i);
            st.pop();
        }
    }
}

후기

최초에 문제를 잘못 읽었고, 이후엔 전체 탐색을 효율적으로 하기위한 노력(가지치기)을 하는 데 시간을 많이 썼음