취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24982번 문제인 Alchemy이다.
문제는 아래 링크를 확인하자.

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

먼저, 주어진 금속으로 K개의 금속 N을 만들 수 있는지 여부를 구할 수 있다면 0 이상 100만 이하의 범위에서 이분탐색을 이용하여 K를 결정지을 수 있다는 점을 관찰하자.

모든 금속의 조합법은 최대 하나만 주어지고 그 금속의 재료는 더 작은 번호의 금속으로만 만들어지므로, N번째 금속서부터 살펴가면서 K개의 금속을 만들기 위해 필요한 만큼의 재료를 최대한 소비하고 더 필요한 만큼을 조합을 통해 얻는 그리디한 방식으로 문제를 해결할 수 있다.

위 과정에서, 조합법이 최악으로 주어질 경우 K개의 금속을 만들기 위한 1번 금속의 필요량이 굉장히 커질 수 있으므로, 오버플로우에 유의하여 구현하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int N;
int arr[101];
vector<int> vec[101];

int tmp[101];

bool func(int val) {
	memset(tmp, 0, sizeof(tmp));
	tmp[N] = val;
	for (int i = N; i > 0; i--) {
		int mn = min(arr[i], tmp[i]);
		tmp[i] -= mn;
		if (tmp[i] && (!vec[i].empty())) {
			for (auto n : vec[i]) tmp[n] = min(tmp[n] + tmp[i], 1000000007);
			tmp[i] = 0;
		}
	}

	for (int i = 1; i <= N; i++) {
		if (tmp[i]) return 0;
	}

	return 1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	int K; cin >> K;
	while (K--) {
		int L, M; cin >> L >> M;
		while (M--) {
			int x; cin >> x;
			if (L <= N) vec[L].emplace_back(x);
		}
	}

	int L = 0, R = 1000000;
	while (L < R) {
		int mid = (L + R) / 2 + 1;
		if (func(mid)) {
			L = mid;
		}
		else {
			R = mid - 1;
		}
	}

	cout << L;
}