📌 문제
루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다. 각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가? 루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.
제약조건
1 ≤ N ≤ 10^6인 정수
1 ≤ W ≤ 10^4인 정수
1 ≤ Mi, Pi ≤ 10^4인 정수
입력형식
첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.
출력형식
첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.
입력예제1
100 2
90 1
70 2출력예제1
170📌 코드
import java.io.*;
import java.util.*;
class Item {
int w;
int p;
public Item(int w, int p) {
this.w = w;
this.p = p;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//배낭의 무게, 귀금속의 종류
StringTokenizer st = new StringTokenizer(br.readLine());
int W = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
ArrayList<Item> items = new ArrayList<>();
for(int i=0; i<N; i++){
st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken()); //금속의 무게
int P = Integer.parseInt(st.nextToken()); //무게당 가격
items.add(new Item(M, P));
}
Collections.sort(items, (i1, i2) -> {
return i2.p - i1.p;
});
int result = 0;
for(Item item : items) {
if(W == 0) break;
if(W >= item.w) { //금속의 무게만큼 담는 경우
result += (item.w * item.p);
W = W - item.w;
} else { //전동톱으로 자르고 담는 경우
result += (W * item.p);
W = 0;
}
}
System.out.println(result);
}
}📌 설명
- 시간복잡도를 생각해보자
N의 범위가 1 ≤ N ≤ 10^6인 정수 으로 되어있습니다. O(n^2)은 되지 않는다는걸 알 수 있습니다. 그렇다면 for문 1개로 문제를 풀 생각을 우선 해봅니다.
- 무슨 알고리즘을 써야 할까?
문제를 읽고, 그리디를 써야하는 것을 알 수 있습니다. 그리디를 사용하기 위해서 우선 정렬을 해줘야하는데, 최대 무게를 구해줘야하므로, 무게를 기준으로 정렬을 해주어야합니다. 그래서 금속의 무게를 기준으로 내림차순으로 정렬을 해주었습니다. 그 후엔, 정렬한 금속을 하나씩 꺼내서, 배낭의 무게 안에 넣을 수 있는 만큼, 금속의 무게가 존재하는만큼 담습니다. 딱 무게가 떨어지지 않더라도 전동톱을 통해 자를 수 있다고 문제에 나와 있으니, 무게가 떨어지지 않은 경우네는, 가방에 남아있는 무게만큼만 전동톱으로 잘라 가방에 넣습니다.
