백준 - 1106 호텔

문제

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

1106번: 호텔

각 도시별 홍보 비용과 이 비용으로 유치할 수 있는 고객이 정해져 있을 때, 호텔 고객을 C명 이상 늘리기 위해 투자해야 하는 비용의 최솟값을 구하는 전형적인 DP 문제였다.

 

문제 풀이

 

점화식을 세워서 dp 값을 계속 갱신했다. i는 비용이고 각 dp[i]의 값은 해당 비용으로 늘릴 수 있는 최대 사람 수로 정했다. 이때 dp 값이 C 이상일 때의 i가 정답이 된다.

dp[i] = max(dp[i-N[0].num]+N[0].cost , ... , dp[i-N[N-1].num]+N[N-1].cost)

 

문제를 풀면서 dp 배열을 너무 작게 만들어서 계속 실패했었다. C가 1000이고 N이 1, 도시의 비용과 고객 수는 100,1일 때 비용이 100000이 되기 때문에 dp 배열은 최대 100000의 크기를 가져야 한다. dp를 풀 때 항상 dp max 값에 유의하자!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>

using namespace std;

/*
i원으로 얻기 가능한 고객 수를 dp로 구하기

dp[i] = max(dp[i-N[0].num]+N[0].cost , ... , dp[i-N[N-1].num]+N[N-1].cost)

*/

#define MAX_DP 100001

int dp[MAX_DP] = { 0 }; //i원으로 얻을 수 있는 고객 수
int C, N;

void printDP() {
	for (int i = 0; i <= C; i++) {
		printf("dp[%d]: %d\n", i, dp[i]);
	}
}
int main()
{


	scanf("%d %d", &C, &N); //만들어야 하는 고객 수, 도시 수
	vector<pair<int, int>> infos(N); //비용, 고객 수

	//dp 초기화
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &infos[i].first, &infos[i].second);
		dp[infos[i].first] = max(dp[infos[i].first], infos[i].second); 
	}

	dp[0] = 0;	

	//dp 구하기
	for (int i = 1; i <= MAX_DP; i++) { //비용
		for (int j = 0; j < N; j++) { //각 도시마다 확인
			int nowCost = infos[j].first;
			int nowPeopleNum = infos[j].second;
			int index = i - nowCost; //현재 비용 사용
			//printf("i: %d index: %d\n", i, index);
			if (index < 0) {
				//printf("continue!!\n");
				continue;
			}

			dp[i] = max(dp[i], dp[index] + nowPeopleNum);
		}
		if (dp[i] >= C) {
			printf("%d\n", i);
			break;
		}
	}

	//printDP();

	return 0;
}

/*
1000 1
100 1
100000
*/