백준 1106번 : 호텔 (C 언어)

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

1106번: 호텔

Code:

#include <stdio.h>
#define max(a,b) (a>b)?a:b
 
int n, c;
int value[1001], count[1001];
int dp[1001*101] = { 0, };
int main()
{
    scanf("%d %d", &c, &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d", &value[i], &count[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= 100000; j++)
        {
            if (j - value[i] >= 0)
            {
                dp[j] = max(dp[j], dp[j - value[i]] + count[i]);
            }
        }
    }
    for (int i = 1; i <= 100000; i++)
    {
        if (dp[i] >= c)
        {
            printf("%d", i);
            break;
        }
    }
}

문제 개요

세계적인 호텔인 형택 호텔의 사장인 김형택은 호텔의 수입을 늘리기 위해 홍보를 하려고 합니다. 홍보 비용과 홍보에 따른 고객 수 증가 정보가 주어지며, 특정 비용에 대해 최소한 C명 이상의 고객을 늘리려고 합니다. 이때, 형택이가 필요한 최소한의 비용을 계산하는 문제입니다.

---

알고리즘 개요

이 문제는 다이나믹 프로그래밍(DP) 알고리즘을 사용하여 해결할 수 있습니다. 다음은 주요 알고리즘 스텝과 코드 설명입니다.

1. 입력 처리: 문제에서 주어진 C와 N 값을 입력받고, 각 도시에서 홍보할 때 드는 비용과 그 비용으로 얻을 수 있는 고객 수를 입력받습니다.
2. DP 배열 초기화: dp 배열을 초기화하고, dp[i]는 비용 i를 사용했을 때 얻을 수 있는 최대 고객 수를 나타냅니다. 초기에는 모든 dp[i]를 0으로 초기화합니다.
3. DP 탐색: 두 개의 반복문을 사용하여 각 도시와 비용에 대한 DP 값을 계산합니다. 첫 번째 반복문은 도시를 순회하고, 두 번째 반복문은 비용을 순회합니다.
   • 현재 비용 j에서 i번 도시를 홍보하는 것이 가능한 경우, dp[j]를 업데이트합니다. 업데이트는 현재 dp[j]와 dp[j - value[i]] + count[i] 중 큰 값을 선택하여 수행합니다.
4. 최소 비용 계산: dp 배열을 탐색하면서, C명 이상의 고객을 늘리기 위한 최소 비용을 찾습니다. dp[i]가 C 이상인 첫 번째 i를 찾으면 해당 비용 i를 출력하고 종료합니다.