[백준] 1038 감소하는 수 - 브루트포스 + 백트래킹 JAVA

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

1038번: 감소하는 수

코드설명

브루트포스와 백트래킹을 활용합니다.

 

처음에는 일종의 DP형태로 DP[1,000,001] 을 선언하고, 1 2 3 4 5->를 증가시키면서 1000001 의 Index를 채울떄까지 완전탐색으로 각 수가 감소하는 수인지 검사하는 방안으로 할려고했습니다.

하지만, 그렇게 할경우 시간초과가 발생할 것 입니다. 

 

두번쨰 방안은, list를 선언합니다.

0 으로 시작하는 모든 감소하는 수, 1로 시작하는 모든 감소하는 수, 2 로 시작하는 모든 감소하는 수... 를 구하기 위한

for(int i=0;i<10;i++) {
    simulate(i);
}
 
public static void simulate(long num) {
    if(num > Long.parseLong("9876543210")) {
        return ;
    }
    answerArr.add(num);
    for(int i=0;i<num%10;i++) {
        simulate((num * 10) + i);
    }
}

위와 같은 알고리즘을 활용합니다.

만약 simulate(5, 1); 이 들어왔다고 가정합니다.

5, 50, 510, 521, 520, 532, 531, 530, 543, 542, 541 .... 54321 이렇게 마무리될 것 입니다.

num%10 을 통해서 현재 자리보다 더 작은 수까지만 simulate를 계속해서 넣어가며 진행한다는 점을 생각해야했습니다.

 

이때, 9876543210 이 감소하는 수중 최대값입니다. 숫자가 0 부터 9 까지밖에 없기 떄문에 이것보다 더 큰 감소하는 수는 없습니다.

answerArr은 가능한 증가하는 수를 모두 계산합니다. 

그러므로 만약 N 보다 answerArr size가 작다면 9876543210 보다 더 큰 수를 N이 원하므로 중단시킵니다.

 

혹은, 9876543210 이 10자리수 이므로 첫번쨰 정답코드처럼 level > 10 이면 중단처리하는 방법도 있습니다.

 

코드

정답코드 최적화코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
	public static int N;
	public static ArrayList<Long> answerArr = new ArrayList<>();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	if(N <= 10) System.out.println(N);
    	else{
    		for(int i=0;i<10;i++) {
    			simulate(i);
    		}
    		
    		if(answerArr.size() <= N) {
    			System.out.println(-1);
    			return ;
    		}
    		Collections.sort(answerArr);
    		System.out.println(answerArr.get(N));
    	}
    	
    }
	public static void simulate(long num) {
		if(num > Long.parseLong("9876543210")) {
			return ;
		}
		answerArr.add(num);
		for(int i=0;i<num%10;i++) {
			simulate((num * 10) + i);
		}
	}
	
}

 

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main {
	public static int N;
	public static ArrayList<Long> answerArr = new ArrayList<>();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	if(N <= 10) System.out.println(N);
    	else{
    		for(int i=0;i<10;i++) {
    			simulate(i, 1);
    		}
    		
    		if(answerArr.size() <= N) {
    			System.out.println(-1);
    			return ;
    		}
    		Collections.sort(answerArr);
    		System.out.println(answerArr.get(N));
    	}
    }
	public static void simulate(long num, int level) {
		if(level > 10 || num > Long.parseLong("9876543210")) {
			return ;
		}
		answerArr.add(num);
		for(int i=0;i<num%10;i++) {
			simulate((num * 10) + i, level + 1);
		}
	}
	
}