[BOJ_1174] 줄어드는 수

설명

---

 

줄어드는 수를 구해놓고 거기서 선택을 하면서 나간다... 이 컨셉을 생각하지 못하면 생각이 나지가 않는다.

 

먼저 9876543210의 형태가 최고 줄어드는 수이고 이때 앞에서 부터 수를 선택해서 나가면 여기서 앞으로는 무조건 줄어드는 수이니... 앞으로 가면된다.

 

그 후에는 뽑을때 순서를 지켜서 오름차순의 순서로 뽑혀야 하니 sort를 하여 꺼내게 된다.

 

처음 접근 법을 제대로 접근을 못해서 시간을 많이 잡아 먹은 문제

 

코드

---

package backtracking;
import java.util.*;
import java.io.*;
public class BOJ_1174 {
    static int N;
    static String[] num = { "9", "8", "7", "6", "5", "4", "3", "2", "1", "0" };
    static List<Long> list;

    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(in.readLine());
        list = new ArrayList<Long>();
        go("0",0);


        Collections.sort(list);
        if(list.size() < N){
            System.out.println(-1);
        }else{
            System.out.println(list.get(N-1));
        }
    }

    private static void go(String str,int idx) {
        if(idx == 10){

            if(!list.contains(Long.parseLong(str))){
                list.add(Long.parseLong(str));
            }
            return;
        }
        go(str + num[idx % 10], idx + 1); //선택 한 경우의 수
        go(str, idx + 1); //선택 한 경우의 수
    }
}