[JAVA] 백준 1038번_감소하는 수

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

1038번: 감소하는 수

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main_1038 {
    static List<Long> numbers = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        if(N < 10) {
            System.out.println(N);
            return;
        } else if (N >= 1023) {
            System.out.println(-1);
            return;
        }
        for (int i = 0; i < 10; i++) {
            search(1, i);
        }
        Collections.sort(numbers);
        System.out.println(numbers.get(N));
    }

    private static void search(int idx, long acc) {
        if(idx > 10) return;
        numbers.add(acc);
        for (int i = 0; i < acc % 10; i++) {
            search(idx + 1, acc * 10 + i);
        }
    }
}

 

# 백트래킹을 활용해서 푸는 문제

• N범위를 일차적으로 걸러줌 : N < 1023
  • 수를 구성하는 숫자는 0 ~ 9, 총 10개 활용 가능
  • 즉 숫자 10개로 만들 수 있는 수 = 각 숫자마다 선택 유무 = 2^10 = 1024
  • 이때, 모든 수를 선택하지 않는 경우 1 제외 -> 총 1023개 가능
• 해당 숫자가 들어가는 자리(idx), 그전에 만들어둔 수를 매개변수로 받는 함수 재귀로 구현
  • idx는 10자리 이하여야 함
  • 그전에 만든 수는 10을 곱해 한자리씩 미뤄준다
  • 바로 앞자리보다 작은 수가 뒤에 와야하므로 0 ~ 기존수%10(=일의 자리) 까지 적용
  • 가능한 모든 감소하는 수를 구한 다음 거기서 N번째 구함