[BJ1038] 감소하는 수

🚩 문제 설명

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

1038번: 감소하는 수

◾ 음이 아닌 정수 X의 자릿수가 가장 큰 수부터 가장 작은 자릿수부터 감소하게 된다.

◾ 자릿수는 각각 한자리에 해당하므로 감소하는 수의 가장 큰 수는 그렇담 9876543210 이 된다.

 

 

---

 

 

 

✅ 입출력

변수 설명
N: 찾아야하는 감소하는 수의 순서
return ➡️ N번째 감소하는 수

✔️ 예제 1

18

42

 

 

---

 

 

 

📑 문제 풀이

with 자바 (Java)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class Main {
	static int ans, N, idx;
	static List<Long> list = new ArrayList<>();


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

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

		if (N <= 10) System.out.println(N);
		else if (N > 1022) System.out.println(-1);
		else {
			for (int i = 0; i < 10; i++) dfs(1, i);
			Collections.sort(list);
			System.out.println(list.get(N));
		}

	} // end main


	private static void dfs(int dep, long n) {
		if (dep > 10) return;

		list.add(n);

		// n보다 작은 값들을 더해준다.
		// n % 10 을 해주는 이유는 마지막 값보다 작아야 하므로
		for (int i = 0; i < n % 10; i++) dfs(dep + 1, (n * 10) + i);

	} // end dfs

}

💬 Point

➡️  List 을 이용하여 감소하는 수를 추가
➡️  수를 하나하나 다 살펴보는 것이 아니라, 감소하는 수만 확인

◾ 하나하나 숫자들을 확인하면서, 감소하는 수를 체크했으나 이러면 시간초과가 난다..

◾ 따라서, 감소하는 수들만 만들어서 리스트에 추가한다.

 

private static void dfs(int dep, long n) {
    if (dep > 10) return;

    list.add(n);

    // n보다 작은 값들을 더해준다.
    // n % 10 을 해주는 이유는 마지막 값보다 작아야 하므로
    for (int i = 0; i < n % 10; i++) dfs(dep + 1, (n * 10) + i);

} // end dfs

◾ 만약 1이 있다면 1과 10 을 추가해주는 형식이다.

◾ 다시 한번 예를 들어, n = 432 이라면 n % 10 이면 2가 되므로 for문에서는 0, 1 이 나오게 된다.

◾ 여기서는 그럼 4320, 4321 을 다음 재귀에서 추가하게 된다.

◾ 이런식으로, 다음 숫자가 앞의 숫자보다 작은 것이 오고 이를 리스트에 추가하여 감소하는 수 리스트를 만든다.

 

public static void main(String[] args) throws Exception {
    System.setIn(new FileInputStream("input2.txt"));
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

    if (N <= 10) System.out.println(N);
    else if (N > 1022) System.out.println(-1);
    else {
        for (int i = 0; i < 10; i++) dfs(1, i);
        Collections.sort(list);
        System.out.println(list.get(N));
    }

} // end main

◾ 해당 리스트를 정렬하고 N번 째의 수를 꺼내준다.

◾ 가장 큰 감소하는 수가 9876543210 이므로 이는 1023 번째의 가장 큰 감소하는 수에 해당한다.

◾ 따라서, 1022 보다 큰 수들은 감소하는 수를 구할 수 없다. 따라서 -1을 바로 출력을 해준다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 백준 감소하는 수 java # 백준 감소하는수 java

# 백준 감소하는 수 자바 # 백준 감소하는수 자바

---