18511 - 큰 수 구성하기

info

• 문제 보기: 18511 - 큰 수 구성하기
• 소요 시간: 37분 25초
• 풀이 언어: java
• 체감 난이도: 3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

bfs 완전탐색

풀이 코드

info

• 메모리: 14760 KB
• 시간: 96 ms

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

public class Main
{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n, k;
    static List<Integer> dList = new ArrayList<>();
    static int ans = -1;
    
    public static void dfs(int curVal) {
        if (curVal > n) return;
        
        ans = Math.max(ans, curVal); // max 값으로 갱신
        
        for (int d : dList) dfs(curVal*10+d);
    }
    
	public static void main(String[] args) throws IOException {
	    input();
	    dfs(0);
	    System.out.println(ans);
	}
	
	public static void input() throws IOException {
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    n = Integer.parseInt(st.nextToken());
	    k = Integer.parseInt(st.nextToken());
	    st = new StringTokenizer(br.readLine());
	    while (st.hasMoreTokens()) {
	        dList.add(Integer.parseInt(st.nextToken()));
	    }
	    dList.sort(Comparator.reverseOrder());
	}
}

풀이 해설

슬픈 능지이슈 🥲

그리디 풀이 1

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

public class Main
{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static String nStr;
    static int k;
    static List<Integer> dList = new ArrayList<>();
    
	public static void main(String[] args) throws IOException {
	    input();
	    
		boolean max = false;
		StringBuilder sb = new StringBuilder();
chfor:	for (char ch : nStr.toCharArray()) {
		    if (max) {
		        sb.append(dList.get(0));
		    }
		    else {
		        for (int i = 0; i < dList.size(); ++i) {
		            if ((ch-'0') == dList.get(i)) {
		                sb.append(dList.get(i));
		                continue chfor;
		            }
		            else if ((ch-'0') > dList.get(i)) {
		                sb.append(dList.get(i));
		                max = true;
		                continue chfor;
		            }
		        }
		        // 숫자 다 찾아봤는데 없으면 문제에선 만족하는 경우만 제공하므로 가장 앞자리에서 0인 경우밖에 없음
		        sb.append('0');
		        max = true;
		    }
		}
		
		System.out.println(Integer.parseInt(sb.toString()));
	}
	
	public static void input() throws IOException {
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    nStr = st.nextToken();
	    k = Integer.parseInt(st.nextToken());
	    st = new StringTokenizer(br.readLine());
	    while (st.hasMoreTokens()) {
	        dList.add(Integer.parseInt(st.nextToken()));
	    }
	    dList.sort(Comparator.reverseOrder());
	}
}

상단의 코드는 다음의 반례가 존재한다.

그리디 풀이 1 반례

100 1
1

그래서 어거지로 계속 그리디로 해결 가능할까 싶어 엣지 처리를 했는데

그리디 풀이 2

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

public class Main
{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static String nStr;
    static int k;
    static List<Integer> dList = new ArrayList<>();
    
	public static void main(String[] args) throws IOException {
	    input();
	    
		boolean max = false;
		StringBuilder sb = new StringBuilder();
chfor:	for (int x = 0; x < nStr.length(); ++x) {
            char ch = nStr.charAt(x);
		    if (max) {
		        sb.append(dList.get(0));
		    }
		    else {
		        for (int i = 0; i < dList.size(); ++i) {
		            if ((ch-'0') == dList.get(i)) {
		                sb.append(dList.get(i));
		                continue chfor;
		            }
		            else if ((ch-'0') > dList.get(i)) {
		                sb.append(dList.get(i));
		                max = true;
		                continue chfor;
		            }
		        }
		        
		        // 숫자 다 찾아봤는데 없으면 문제에선 만족하는 경우만 제공하므로 가장 앞자리에서 0인 경우밖에 없음
		        if (x == 0) { // 첫자리
		            //sb.append('0');
		            max = true;
		        }
		        else { // 100 1 1 같은 경우임 -> 그냥 한자리 버리고 max로 다 채운 값이 정답으로 즉시 결정됨
		            int len = nStr.length()-1;
		            sb = new StringBuilder();
		            while (len-- > 0) sb.append(dList.get(0));
		            break;
		        }
		    }
		}
		
		System.out.println(Integer.parseInt(sb.toString()));
	}
	
	public static void input() throws IOException {
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    nStr = st.nextToken();
	    k = Integer.parseInt(st.nextToken());
	    st = new StringTokenizer(br.readLine());
	    while (st.hasMoreTokens()) {
	        dList.add(Integer.parseInt(st.nextToken()));
	    }
	    dList.sort(Comparator.reverseOrder());
	}
}

...그래도 반례가 존재한다.

그리디 풀이 2 반례

543 2
5 4

그래서 두번째 반례를 보면 느낌이 오겠지만 이 문제는 무조건 백트래킹 기법이 필요하다.

메모

• 숫자 개수를 최대 3개까지만 주고, 최악의 경우 9자리에 대해서 모든 경우를 맞춰보면 되기에 완탐도 통과하는 문제이다.