백준 1174[자바] java 줄어드는 수

문제 링크: https://www.acmicpc.net/problem/1174

1174번: 줄어드는 수

▶문제

음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다.

N번째로 작은 줄어드는 수를 출력하는 프로그램을 작성하시오. 만약 그러한 수가 없을 때는 -1을 출력한다. 가장 작은 줄어드는 수가 1번째 작은 줄어드는 수이다.

▶입력

N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

▶출력

첫째 줄에 N번째 작은 줄어드는 수를 출력한다.

▶해설

DP관련 문제인줄 알았지만 만들어질 수 있는 가장 큰 수가 9876543210이므로 전체 경우의 수를 구하는 백트래킹으로 풀었습니다. 조건을 살펴보겠습니다. 

 

1. 왼쪽에서부터 자리가 감소하는 수여야한다. 

2. 9876543210이 가장 큰 감소하는 수이다.

 

현재 숫자를 선택하는 경우와 현재 숫자를 선택하지 않는 경우의 수로 나뉩니다. 이때 현재 숫자의 Index는 0~9로 거꾸로된 배열로 선택합니다. 

arr = {9,8,7,6,5,4,3,2,1,0}

private static void dfs(long num, int index){

	// arr의 배열은 길이가 10이므로 index가 길이 10보다 같거나 크면 종료 
	if(index>=10){
        return;
    }

    // 해당 숫자를 선택하고, Index를 1 키운다.
    dfs((num*10)+arr[index], index+1);
    // 해당 숫자를 선택하지 않고, Index를 1 키운다.
    dfs(num,index+1);

}

 

선택된 숫자들은 List<>에 담아줍니다. 

if(!list.contains(num)){
    list.add(num);
}

 

숫자들은 크키 순서로 들어가 있지 않기 때문에 dfs함수가 모두 끝난뒤 정렬을 해줍니다. 

list.sort(null);

 

이렇게 되면 list.get(N-1)이 최종적인 정답이 됩니다. 하지만 N-1이 list의 size와 크거나 같은 경우는 존재하지 않는 수이므로 -1로 출력하게 예외 처리합니다. 

try{
    System.out.println(list.get(n-1));
}catch (Exception e){
    System.out.println(-1);
}

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

    static int n;
    static int [] arr = {9,8,7,6,5,4,3,2,1,0};
    static List<Long> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        dfs(0,0);
        list.sort(null);


        try{
            System.out.println(list.get(n-1));
        }catch (Exception e){
            System.out.println(-1);
        }

    }

    private static void dfs(long num, int index){
        if(!list.contains(num)){
            list.add(num);
        }

        if(index>=10){
            return;
        }

        dfs((num*10)+arr[index], index+1);
        dfs(num,index+1);

    }
}