[백준] 1082번 방 번호 (JAVA)

1082번: 방 번호

가장 큰 수를 만들기 위한 우선순위는 아래와 같다.

 

1. 자릿수가 최대한 길어야 한다.

2. 맨 앞자리부터 최대한 큰 수가 들어가 있어야 한다.

 

먼저 1번을 만족하려면 무조건 숫자를 많이 모아야 하기 때문에

비용이 가장 적은 숫자를 최대한 많이 산다.

이때, 비용이 가장 적은 숫자가 0이라면

맨 앞자리에 0이 오면 안 되므로

비용이 두 번째로 적은 숫자를 하나 사서

맨 앞자리에 배치한 다음에

나머지는 비용이 가장 적은 숫자로 채운다.

 

2번을 만족하기 위해서는

1번에서 만들어진 수를 가져와서

맨 앞자리부터 맨 끝자리까지 최대한 큰 수로 교체해야 한다.

맨 앞자리엔 0이 오지 않게 주의하고

수용 가능 가격 범위를 넘지 않은 선에서

가장 큰 숫자부터 차례로 교체를 시도한다.

 

1, 2번 과정을 마치면 최종 결과가 나온다.

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

class number{
	int num, price;
	number(int num, int price) {this.num = num; this.price = price;}
}

public class BOJ_1082_방번호 {
	private static int N, pocket;
	private static int res[] = new int[100];
	private static number arr[];
	private static Map<Integer, Integer> m = new HashMap<>(); // 숫자-비용 따로 저장해두려고
	
	public static void main(String[ ] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); arr = new number[N];
		for(int i = 0; i < N; i++) {
			arr[i] = new number(i, sc.nextInt());
			m.put(i, arr[i].price);
		}
		pocket = sc.nextInt();
		
		Arrays.sort(arr, new Comparator<number>() { // 가격 기준 오름차순 정렬
			@Override
			public int compare(number o1, number o2) {
				if(o1.price == o2.price) return o1.num - o2.num;
				return o1.price - o2.price;
			}
			
		});
		
		int cnt = 0;
		if(arr[0].num == 0) { // 숫자 0이 가장 작은 수라서 맨 앞에 올 수 없기 때문에
			if(N == 1 || arr[1].price > pocket) { // 0대신 넣을 그 다음 숫자의 비용을 감당할 수 없다면
				System.out.println(0); // 숫자 0으로밖에 할 수 없을 때 답은 0
				System.exit(0);
			}
			res[cnt++] = arr[1].num; // 그 다음 숫자의 비용을 감당할 수 있으면 이 숫자로 맨 앞자리 채운다
			pocket -= arr[1].price;
		}
		
		while(pocket - arr[0].price >= 0) { // 가장 비용이 작은 숫자로 최대한 많이 채움
			res[cnt++] = arr[0].num;
			pocket -= arr[0].price;
		}
		
		for(int i = 0; i < cnt; i++) {
			for(int j = N - 1; j >= 0; j--) { // 가장 큰 수부터
				if(i == 0 && j == 0) continue; // 맨 앞자리에 0이 들어가면 안 됨
				int tmp = pocket + m.get(res[i]) - m.get(j);
				if(tmp >= 0) { // 가격 범위 안 넘어서 현재 숫자로 바꿀 수 있으면 바꿈(최대한 큰 수이므로)
					pocket = tmp; // 허용 가능한 비용 갱신
					res[i] = j;
					break;
				}	
			}
		}
		
		for(int i = 0; i < cnt; i++) System.out.print(res[i]);
	}
}