[BOJ 1106] 호텔
- 문제풀이
문제
세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.
형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.
예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.
각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
풀이
적어도 $C$명의 고객을 유치하기 위해 소요되는 최소 비용을 산출하는 문제이다. 각 도시별 홍보 비용과 그에 따른 고객 유치 수가 주어지며, 각 도시에는 무한한 잠재 고객이 존재하므로 동일한 항목을 중복하여 선택할 수 있는 냅색 알고리즘의 전형적인 형태를 띤다. 이를 효율적으로 해결하기 위해 다이나믹 프로그래밍 기법을 적용한다.
구현 전략은 다음과 같다:
- 상태 정의: $DP[i]$를 정확히 $i$명의 고객을 확보하는 데 필요한 최소 비용으로 정의한다.
- 초기화: $DP[0]$은 $0$으로 설정하며, 그 외의 모든 요소는 충분히 큰 상수인 $INF$($987\,654\,321$)로 초기화하여 최솟값 갱신을 준비한다.
- 전이 식: 각 도시의 비용($cost$)과 고객 수($customer$) 정보를 바탕으로 다음과 같은 점화식을 수행한다:
- 조건 최적화: “적어도 $C$명”이라는 제약 조건에 따라, 정확히 $C$명을 유치하는 경우뿐만 아니라 $C$명을 초과하여 유치하는 비용이 더 저렴한 경우까지 고려해야 한다. 따라서 소스 코드에서는 목표치인 $C$를 달성하거나 초과할 수 있는 모든 경로에 대해 최솟값을 지속적으로 갱신하도록 설계되었다.
고객 목표 수 $C$는 최대 $1\,000$이며 홍보 가능한 도시의 개수 $N$은 $20$ 이하이다. 따라서 전체 시간 복잡도는 $O(CN)$이며, 이는 약 $20\,000$회의 연산을 수행하므로 제한 시간 $2$초 내에 충분히 해결 가능하다.
소스코드
Github Link : Source Code
참고 알고리즘 : 냅색 알고리즘