백준 1038번
https://www.acmicpc.net/problem/1038

문제

---

생각하기

---

• 백트래킹을 통해서 부분조합을 만들어낸다.

• 0~9까지의 숫자로 10자리를 만들 수 있는 방법은 2^10으로 총 1024가지 이다.

  • 하지만, 아무것도 선택하지 않는 1가지 방법을 제외하여 1023가지가 된다.
  • 고로, N이 1023 이상일 경우 우리는 감소하는 숫자를 만들 수 없다.

• 모듈러 연산과, 10의 배수로 증가하되, 자신은 포함하지 않는 것이 핵심인 것 같다.

동작

		for(int i = 0; i < 10; i++) {
			DFS(i);
		}

0부터 시작해서 만들 수 있는 숫자를 하나씩 모두 증가하며 만든다.

DFS(0)은 실행된 후 list에 0을 삽입하고,

		long modValue = num % 10;
		if(modValue == 0) {
			return;
		}

mod가 0이므로 조건에 걸려서 return 된다.

DFS(1)은 먼저 list에 1을 삽입하고 for문에서 i-1을 하여 0으로 DFS(10)이 실행된다.
list에 10을 삽입, 10 % 10은 0이므로 조건에 걸려 return 된다.

코드

---

Java

감소하는 방향

import java.util.*;
import java.io.*;

public class Main {
	static List<Long> list = new ArrayList<>();
	static int N;
	static int count = 0;

	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.print(N);
			return;
		} else if (N >= 1023) {
			System.out.print(-1);
			return;
		}

		for(int i = 0; i < 10; i++) {
			DFS(i);
		}

		Collections.sort(list);
		System.out.print(list.get(N));
	} // End of main

	private static void DFS(long num) {		
		list.add(num);		
		long modValue = num % 10;
		if(modValue == 0) {
			return;
		}
		
		for(long i=modValue-1; i>=0; i--) {
			long newValue = num * 10 + i;
			DFS(newValue);
		}
	} // End of DFS
} // End of Main class

증가하는 방향

import java.util.*;
import java.io.*;

public class Main {
	static List<Long> list = new ArrayList<>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		if (N <= 10) {
			System.out.println(N);
			return;
		} else if(N >= 1023) {
			System.out.println(-1);
			return;
		}
		
		for(int i=0; i<10; i++) {
			DFS(i, 1);
		}
		
		Collections.sort(list);
		System.out.println(list.get(N));
	} // End of main

	private static void DFS(long num, int idx) {
		if (idx > 10)
			return;

		list.add(num);
		for (int i = 0; i < num % 10; i++) {
			DFS((num * 10) + i, idx + 1);
		}

	} // End of DFS
} // End of Main class