문제
세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.
형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.
예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.
각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
풀이
도시별 홍보는 여러 번 사용할 수 있으므로 전형적인 무한 배낭 문제로 볼 수 있다. 다만 정확히 C명을 맞출 필요는 없고, C명 이상만 만들면 되므로 목표 고객 수를 조금 넘는 경우까지 같이 봐야 한다.
코드에서는 dp[x]를 고객을 정확히 x명 늘리는 데 드는 최소 비용으로 두고, 초기값을 큰 수로 채운 뒤 dp[0] = 0으로 시작한다. 각 도시의 (cost, person) 정보를 읽을 때마다 j = person부터 끝까지 돌면서 dp[j] = min(dp[j], dp[j - person] + cost)로 갱신한다. 같은 도시를 여러 번 사용할 수 있으므로 증가 방향으로 순회하는 것이 맞다.
정답은 dp[C] 하나가 아니라 dp[C] 이상 구간의 최솟값이다. 그래서 코드에서도 C + 101 정도까지 배열을 잡아 두고, 마지막에 C 이상인 모든 값 중 가장 작은 비용을 선택한다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int C = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
// 고객 수는 초과 가능, C 값을 뛰어 넘을 때도 생각
int maxPerson = C + 101;
int[] dp = new int[maxPerson];
// 그냥 Integer.MAX_VALUE로 두면 터짐
Arrays.fill(dp, Integer.MAX_VALUE - 101);
dp[0] = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int cost = Integer.parseInt(st.nextToken());
int person = Integer.parseInt(st.nextToken());
// 특정 인원 수 일 때 가지는 최솟값 계산
for (int j = person; j < maxPerson; j++)
dp[j] = Math.min(dp[j], cost + dp[j - person]);
}
int ans = Integer.MAX_VALUE;
// C 값을 뛰어 넘는 것까지 생각
for (int i = C; i < maxPerson; i++)
ans = Math.min(ans, dp[i]);
System.out.println(ans);
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
정확히 맞추는 문제가 아니라 넘겨도 되는 배낭 문제라는 점이 중요하다. 목표 고객 수를 살짝 초과하는 경우까지 포함해서 보면 구현이 훨씬 자연스럽다.
