취미로 코딩하기

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

이번에 볼 문제는 백준 26937번 문제인 Köpa Böcker이다.
문제는 아래 링크를 확인하자.

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

M이 최대 15까지이므로, 물건을 살 서점을 고를 경우의 수는 많아야 2^15가지가 된다.

위의 각 경우에 대하여 골라진 서점 중 각 책의 값의 최솟값들의 합(살 수 없다면 가상의 무한대값)을 더해 각 제한 하에서의 답을 구하자. 이 값들 중 최솟값이 문제의 답이 됨을 이용해 문제를 해결하자.

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

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

vector<int> mn[100];
int arr[15][100]; // [i][j]: i번 서점의 책 j의 값
int p[15];
int N, M;

int sum_p;
int ans = 2000000007;

void func(int cur) {
	if (cur == M) {
		int val = sum_p;
		for (int n = 0; n < N; n++) {
			val += mn[n].back();
		}
		ans = min(ans, val);
		return;
	}

	func(cur + 1);
	sum_p += p[cur];
	for (int n = 0; n < N; n++) {
		if (mn[n].back() >= arr[cur][n]) mn[n].emplace_back(arr[cur][n]);
	}
	func(cur + 1);
	for (int n = 0; n < N; n++) {
		if (mn[n].back() == arr[cur][n]) mn[n].pop_back();
	}
	sum_p -= p[cur];
}

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

	cin >> N >> M;
	
	for (int n = 0; n < N; n++) {
		mn[n].emplace_back(10000007);
		for (int m = 0; m < M; m++) arr[m][n] = 1000000007;
	}
	for (int m = 0; m < M; m++) {
		int K; cin >> K >> p[m];
		while (K--) {
			int x, y; cin >> x >> y; x--;
			if (y < arr[m][x]) arr[m][x] = y;
		}
	}

	func(0);

	cout << ans;
}