[백준]1106번 호텔 - C/C++

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

1106번: 호텔

문제

세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.

형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.

예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.

각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

---

 기본적인 냅색 문제이다.

dp[ 비용 ] = 해당 비용으로 얻을 수 있는 '고객'의 최댓값

으로 설정하여 문제를 풀 수 있다.

#include <iostream>
#include <string.h>
#include <algorithm>

using namespace std;

int c, n;
pair <int, int> arr[21];
int dp[100001] = {0};

int main() {
	cin >> c >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i].first >> arr[i].second; // first : cost / second : client
	

	for (int i = 0; i < n; i++) {
		for (int j = arr[i].first; j < 100001; j++) {
			dp[j] = max(dp[j], dp[j - arr[i].first] + arr[i].second);
		}
	}

	for (int i = 0; i < 100001; i++) {
		if (dp[i] >= c) {
			cout << i;
			break;
		}
	}

	return 0;
}

---

    처음에는 dp[고객] = 해당 숫자의 고객을 유치할 수 있는 최소 비용으로 dp배열을 설정하였다. 한 비용으로 살 수 있는 고객의 수는 나눠지지 않으므로 index를 N번째 고객의 단위로 증가시켜 가며 dp 배열을 저장해나갔다. 이러한 방식으로 예제의 답까지 잘 나와서 제출을 해보았는데 틀렸습니다가 나왔다. 그래서 질문 게시판에 있는 반례들도 확인을 해보았지만 반례들이 부족했는지 다 잘 나왔다.

    그래서 문제를 접어두고 며칠이 지나 오늘 질문 게시판을 한번 더 들어갔는데 새로운 글에 반례가 안되었던 것이다. 다시 곰곰히 생각해보니 이렇게 고객의 수로 index를 증가시켜나가면 겹치는 경우를 계산하지 못했던 것인데 예시의 경우 나이스 하게 숫자가 작아 그러한 부분들을 확인할 수 없었던 것이다.

    그래도 며칠전에 계속 고민했는데도 답이 안나왔는데 이번에는 시작하자 마자 틀린 부분을 찾게 되었다. 역시 코딩은 안풀릴때는 잠시 접어두고 다음번에 오면 쉽게 풀리는것 같다.