[백준] 18511 큰 수 구성하기 - 완전탐색 + 문자열 JAVA

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

18511번: 큰 수 구성하기

문제풀이

완전탐색 문제였습니다.

처음에, 틀렸었던 부분은 K가 1, 3, 5 라고할대 135, 153, 315, 351, 513, 531 이런식으로 나올수 밖에 없게 Visited를 사용해서 처리해서 그렇습니다.

이후에 Visited를 제거하여 111 115 ... 이런식으로 모든 조합을 구하도록 설정했습니다.

public static void simulate(StringBuilder sb, int level) {

    if(level > 0) {
        int a = Integer.parseInt(sb.toString());
        if(a > N) return;
        if( a <= N) {
            result = Math.max(result,  a);
        }    		
    }

    for(int i=0;i<K;i++) {
    	//if(visited[i] == false){
        	//visited[i] = true;
        	sb.append(map[i]);
        	simulate(sb, level + 1);
        	sb.deleteCharAt(sb.length()-1);
          //  visited[i] = false;
        //}
    }

}

 

 

또한 문제에서 보면 처음에 K가 1, 3, 5 일경우 3자리수만 만들어지는 줄알았지만

K가 1, 3, 5 인것은 해당 숫자가 1, 3, 5 로만 이루어져있다는 것이지 자리수와는 상관이 없었습니다.

 

그렇기에 sb가 "" 인경우는 제외하기 위해 level > 0 인경우만 탐색하고

만약 a가 N보다 커지는 상황이라면 바로 상황을 종료하고,

a 가 N보다  작은경우에 최대값을 갱신하도록 하여 모든 경우를 검사하도록 했습니다.

이렇게 할경우에도 시간초과가 나지 않는 이유는, 

문제의 조건을 보면

• (10 ≤ N ≤ 100,000,000, 1 ≤ K의 원소의 개수 ≤ 3)

N은 최대 1억입니다. K의 원소의 개수는 1가지부터 3가지뿐입니다. 그렇기에 K는 3가지의 숫자로 8가지의 자리수만 선택하면 되니, O(3^8) 의 시간이 나오기에 완전탐색로 해결할 수 있습니다.

if(level > 0) {
    int a = Integer.parseInt(sb.toString());
    if(a > N) return;
    if( a <= N) {
        result = Math.max(result,  a);
    }    		
}

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static int N, K;
	public static int[] map;
	public static int result = 0;
	public static boolean[] visited;
	
    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());
    	K = Integer.parseInt(st.nextToken());
    	
    	map = new int[K];
    	visited = new boolean[K];
    	
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<K;i++) {
    		map[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	
    	simulate(new StringBuilder(), 0);
    	System.out.println(result);
    }
    
    public static void simulate(StringBuilder sb, int level) {
    	
    	if(level > 0) {
        	int a = Integer.parseInt(sb.toString());
        	if(a > N) return;
    		if( a <= N) {
    			result = Math.max(result,  a);
    		}    		
    	}

    	for(int i=0;i<K;i++) {
			sb.append(map[i]);
			simulate(sb, level + 1);
			sb.deleteCharAt(sb.length()-1);
    	}
    	
    }
    
}