[백준] 1106번 - 호텔 (C++)

1106번: 호텔

문제

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

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

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

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

 

입력

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

 

출력

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

풀이과정

해당 문제는 dp형식으로 접근할 수 있는 문제였었고,

메인으로 구성했던 로직은 

std::min(min, dp[i - city[j][1]] + city[j][0]);

형식으로 n으로 들어온 모든 값들을 돌며 가장 작은값에 살을 붙여나가는 방식으로 dp를 구성하였다.

 

code

#include <iostream>

const int	INF = 10000;

int		city[21][2];
int		dp[INF];

// 0 : [비용]
// 1 : [고객의 수]
int		main(void)
{
	int c, n, min, num, cost;

	std::cin >> c >> n;
	for (int i = 1; i <= n; i++) {
		std::cin >> city[i][0] >> city[i][1];
	}
	for (int i = 1; i <= INF; i++) {
		min = 1000000;
		for (int j = 1; j <= n; j++) {
			if (i == city[j][1]) 
				min = std::min(min, city[j][0]);
			if (1 <= i - city[j][1]) 
				min = std::min(min, dp[i - city[j][1]] + city[j][0]);
		}
		dp[i] = min;
	}
	min = 1000000;
	for (int i = c; i < INF; i++) {
		min = std::min(min, dp[i]);
	}
	std::cout << min;

	return (0);
}

 

후기

문제에서 제대로된 기준을 주지않아서 문제는 푸는데 난항이 있었던거같다.

조건만 깔끔하게 줬으면 더 좋았을걸