문제

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

스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이다.

문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 숫자를 구매할 수 있다. 방 번호가 0이 아니라면 0으로 시작할 수 없다.

예를 들어, N = 3, M = 21, P0 = 6, P1 = 7, P2 = 8이라면, 만들 수 있는 가장 큰 방 번호는 210이다. 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 구해보자.

---

입력

첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다.

---

출력

첫째 줄에 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호를 출력한다. 적어도 하나의 숫자를 살 수 있는 입력만 주어진다.

---

풀이

접근방법

시간제한 2초, 메모리 128MB이다.
1 ≤ N ≤ 10
1 ≤ Pi ≤ 50
1 ≤ M ≤ 50

성냥개비 문제와 유사하다는 생각이 들었다.
https://velog.io/@hyeokkr/%EB%B0%B1%EC%A4%803687-%EC%84%B1%EB%83%A5%EA%B0%9C%EB%B9%84-with-Java

DP로 풀려고 보니 시간제한이 N, M 크기에 비해 넉넉하다.
그리디 하게 접근해 보자.

가장 큰 수를 만든다는것 = 가장 저렴한 숫자를 많이 사서 자릿수를 늘리는것
즉, 전체 비용 / 가장 저렴한 비용 = 전체 자리수

전체 자릿수를 구하고, 가장 저렴한 숫자로 가득 채워보자.
다만, 첫 번째 자리는 0이 될 수 없으므로 별도의 작업이 필요하다.

3
6 7 8
21
-> 100

6이 가장 저렴하나, 0이므로 첫 자리가 될 수 없다.
그 다음 저렴한 1(비용7)이 첫 자리가 되어야한다.
100 (7+6+6)로 최대 자리수를 만들고 기본값을 채웠다.

현재 100이라는 수를 만들기 위해 19원의 비용을 지불했다.
가장 큰 수를 만들기 위해서 남은 돈을 이용해서 가장 앞자리 부터 큰수로 변경한다.

수(비용)
100 (19) -> 200 (20) > 210 (21)

더이상 변경할 수 없는 큰 수가 없다면, 다음 자리수로 이동한다.
비용을 다 사용하거나, 가장 끝자리까지 갔다면, 가장 큰 수가 완성되었다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
	static int N, target;
	static List<Pair> list;

	static class Pair implements Comparable<Pair> {
		int number;
		int cost;

		Pair(int a, int b) {
			number = a;
			cost = b;
		}

		@Override
		public int compareTo(Pair o) {
			if (this.cost == o.cost)
				return o.number - this.number;
			return o.cost - this.cost;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = stoi(in.readLine());

		int[] cost = new int[N];

		list = new ArrayList<>();
		String[] splitedLine = in.readLine().split(" ");
		for (int i = 0; i < N; ++i) {
			int value = stoi(splitedLine[i]);
			cost[i] = value;
			list.add(new Pair(i, value));
		}

		Collections.sort(list);
		target = stoi(in.readLine());

		if (N == 1) {
			System.out.println(0);
			return;
		}

		String base = "";
		int length = 0;
		if (list.get(N - 1).number == 0) {
			int tempCost = target - list.get(N - 2).cost;
			if (tempCost < 0) {
				// 두번째로 저렴한것이 전체 비용보다 비싼경우
				System.out.println(0);
				return;
			}
			base += Integer.toString(list.get(N - 2).number);
			length = tempCost / list.get(N - 1).cost;
			for (int i = 0; i < length; ++i)
				base += Integer.toString(list.get(N - 1).number);
			target = tempCost - list.get(N - 1).cost * length;
		} else {
			length = target / list.get(N - 1).cost;
			for (int i = 0; i < length; ++i)
				base += Integer.toString(list.get(N - 1).number);
			target = target - list.get(N - 1).cost * length;
		}

		char[] arr = base.toCharArray();
		for (int i = 0; i < base.length(); i++) {
			int curNumberCost = cost[arr[i] - '0'];
			for (int j = N - 1; j >= 0; j--) {
				if (target - (cost[j] - curNumberCost) >= 0) {
					target = target - (cost[j] - curNumberCost);
					arr[i] = (char)(j + '0');
					break;
				}
			}
		}
		System.out.println(arr);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}