[Algorithm Problem] 호텔 (BAEKJOON: 1106)

호텔 (BAEKJOON: 1106)

이번 문제는 0-1 Knapsack Problem이라는 유형이었는데, 처음 문제를 풀 때에는 Fractional Knapsack Problem처럼 풀었다가 틀렸었다. 분명 DP 유형은 맞는데 어떻게 접근해야 하는지를 고민하다가 동탄행 M4108 버스에서 BFS와 DP를 합치면 푸는 아이디어를 떠올렸다.

Dynamic Programming(동적 계획법)의 핵심은 같은 연산을 두 번 하지 않는 것이라고 생각한다. 이 문제에서는 홍보에 따른 고객 숫자가 배열의 인덱스가 되고, 해당 인덱스에는 그 값에 도달하기 까지 필요한 최소 홍보 비용이 저장되어 있다. BFS 탐색 과정 중 내가 i명의 고객 숫자를 확보해도 홍보 비용이 이전에 도달했던 숫자보다 크다면 그 다음 연산은 두 번 반복하지 않는 것이다.

풀이

#include<iostream>
#include<queue>

#define MAXVAL 1000001
using namespace std;

int C, N;
int dp[2000]; // dp[i] : i명 늘리기 위해 필요한 최소 C

struct point {
	int cost;
	int people;

public:
	point() {
		cost = MAXVAL;
		people = MAXVAL;
	}

	point(int c, int p) {
		this->cost = c;
		this->people = p;
	}
} p[25];

int main(int argc, char* argv[]) {
	cin >> C >> N;
	for (int i = 0; i < N; i++) cin >> p[i].cost >> p[i].people;

	int ans = MAXVAL;
	for (int i = 0; i < 2000; i++) dp[i] = MAXVAL;

	queue<point> q;
	q.push(point(0, 0));

	while (!q.empty()) { 
		point tmp = q.front();
		q.pop();

		if (C <= tmp.people) {
			if (tmp.cost < ans) ans = tmp.cost;
			continue;
		}

		for (int i = 0; i < N; i++) {
			int tcost = tmp.cost + p[i].cost;
			int tpeople = tmp.people + p[i].people;

			if (tcost < dp[tpeople]) {
				dp[tpeople] = tcost;
				q.push(point(tcost, tpeople));
			}
		}
	}

	cout << ans;

	return 0;
}