취미로 코딩하기

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

이번에 볼 문제는 백준 25330번 문제인 SHOW ME THE DUNGEON이다.
문제는 아래 링크를 확인하자.

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

마을의 방문 순서에 관계없이, 구할 마을을 고를 경우의 수는 2^20 = 1048576가지이다. 이 각각의 경우에 대해 각 집합에 들어있는 마을들을 전부 구하기에 체력이 충분한지 여부와 주민수의 합을 구해 문제를 해결하자.

마을들을 미리 정해뒀을 때, 공격력이 약한 몬스터가 있는 마을부터 greedy하게 방문하는 것이 체력을 가장 적게 소모하는 방법이된다. 총 V개의 마을을 방문할 때, 시루의 체력은 각 i에 대해 (i번째로 방문한 마을의 몬스터의 공격력) * (V - i)만큼 필요하다는 점을 이용하면 위의 방문순서가 최적임을 쉽게 증명할 수 있다.

위의 내용들을 이용해, 각 마을에 있는 몬스터의 공격력을 기준으로 마을들을 미리 정렬해두면 매번 새로 정렬할 필요 없이 완전탐색으로 문제를 간단히 해결할 수 있게 된다.

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

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

int N, K;
pair<int, int> p[20];

int asum, psum;
int ans = 0;

void func(int ith) {
	ans = max(ans, psum);
	if (ith < N) {
		func(ith + 1);
		int& A = p[ith].first, & P = p[ith].second;
		if (K >= asum + A) {
			asum += A;
			K -= asum;
			psum += P;
			func(ith + 1);
			psum -= P;
			K += asum;
			asum -= A;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> p[i].first;
	for (int i = 0; i < N; i++) cin >> p[i].second;
	
	sort(p, p + N);

	func(0);

	cout << ans;
}