소프티어(Softeer) 금고털이 (C++)

요약

cost를 인덱스로 하는 safe라는 배열을 만들어서 무게만큼의 값을 부여했다.

---

문제

배낭은 W ㎏까지 담을 수 있다.
각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?
귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

[제약조건]
1 ≤ N ≤ 106인 정수
1 ≤ W ≤ 104인 정수
1 ≤ Mi, Pi ≤ 104인 정수

[입력]
첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다.
i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.

[출력]
배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

---

풀이

#include <iostream>
using namespace std;

int W, N;
int safe[10001] = { 0, };
int maxcost;

void init() {
	cin >> W >> N;
	for (int i = 0; i < N; i++) {
		int m, cost;
		cin >> m >> cost;
		safe[cost] += m;
		if (cost > maxcost) maxcost = cost;
	}
}

int thief() {
	int rest = W;
	int money = 0;
	for (int i = maxcost; i >=0 ; i--) {
		if (safe[i] == 0) continue;
		int now = safe[i];
		if (rest > now) {
			rest -= now;
			money += i * now;
		}
		else if (rest == now) {
			rest -= now;
			money += i * now;
			return money;
		}
		else {
			money += i * rest;
			return money;
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie();
	cout.tie();

	init();
	int ans = thief();
	cout << ans;

	return 0;
}