문제 링크
문제
티어: 골드 3
알고리즘: 그리디
스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 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원을 사용해서 만들 수 있는 가장 큰 방 번호를 출력한다. 적어도 하나의 숫자를 살 수 있는 입력만 주어진다.
제한
풀이
구하고자 하는 것은 최대 M원을 사용해서 만들 수 있는 가장 큰 방 번호이다.
일단 N이 10보다 작거나 같다. 브루트 포스로 풀 수 있는지 생각해 봤다. 10^10이기 때문에 불가능하다.
그러면 가장 큰 방 번호를 만들려면 어떻게 해야 할까?
-
길이를 최대한 늘여야 한다.
-
가중치가 큰 자릿수부터 가능한 가장 큰 값으로 대체해야 한다.
길이를 최대한 늘리기 위해서 가장 작은 값으로 구성하면 길이를 최대로 늘릴 수 있다.
이때 주의할 점은 번호가 0인 물품이 가장 작은 값일 때는 가장 앞자리가 그다음으로 작은 값을 가져야 한다.
ex) 000 -> 100
그러면 현재 M원으로 길이를 최대한으로 늘린 상태에서 가중치가 큰 자릿수부터 가능한 가장 큰 물품 번호로 대체하면 된다. 총 50자리라고 해도 N은 10이기 때문에 O(N*M) 풀이가 가능하다.
예제 입력 1로 답을 구해보면
3
6 7 8
21길이를 최대한 늘였을 때 선택된 방 번호는 100이고, 총가격은 19이다.
맨 앞자리부터 가능한 가장 큰 물품 번호로 대체하면
100 에서 200이 가능하다. 21(M) - (19 - 7) = 9 >= 8(2번 물품 가격)
다음 십의 자리를 대체하면
200에서 210이 가능하다. 21(M) - (20 - 6) = 7 >= 7(1번 물품 가격)
현재 총가격이 21원이기 때문에 210이 답이다.
푼 시간: 01:00
import java.io.*;
import java.util.*;
class Product implements Comparable<Product> {
int p, n;
Product(int p, int n) {
this.p = p;
this.n = n;
}
@Override
public int compareTo(Product o) {
if(this.p < o.p) {
return 1;
} else if(this.p > o.p) {
return -1;
}
return 0;
}
}
public class Main {
static int N, M;
static Product[] list, numOrderList;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
list = new Product[N];
numOrderList = new Product[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
Product pd = new Product(Integer.parseInt(st.nextToken()), i);
list[i] = pd;
numOrderList[i] = pd;
}
Arrays.sort(list);
M = Integer.parseInt(br.readLine());
Stack<Product> stack = new Stack();
init(stack);
if(stack.peek().n == 0) {
System.out.println("0");
} else {
System.out.println(answer(stack));
}
}
static String answer(Stack<Product> stack) {
int curV = 0;
for(Product p: stack) {
curV += p.p;
}
StringBuilder sb = new StringBuilder();
while(stack.size()!=0) {
Product top = stack.pop();
curV -= top.p;
int left = M - curV;
for(int i=numOrderList.length - 1; i>=0; i--) {
if(left >= numOrderList[i].p) {
sb.append(numOrderList[i].n);
curV += numOrderList[i].p;
break;
}
}
}
return sb.toString();
}
static void init(Stack<Product> stack) {
int mo = M;
Product fst = list[N-1]; //가장 가격이 작은 물품
if(fst.n == 0 && N != 1) {
Product sec = list[N-2];
while((mo - sec.p) >= 0) {
stack.push(fst);
mo -= fst.p;
}
if(stack.size() != 0) {
stack.pop();
stack.push(sec);
} else {
stack.push(fst); //이때는 답이 0
}
} else {
while((mo - fst.p) >= 0) {
stack.push(fst);
mo -= fst.p;
}
}
}
}