BOJ 1106

문제링크

링크텍스트

시간제한 2초 메모리제한 128MB

문제

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

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

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

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

입력

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

출력

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

문제읽고 스케치

문제를 읽고 들었던 생각은 배낭문제와 유사한거 같다는 것이다. 최소한의 비용으로 최대화하는 방법인데 DP를 이용하면 풀릴꺼라 생각했다. result로 나올 수 있는 최대값은 c가 1000이고 그 비용으로 얻을 수 있는 고객의 수는 100보다 작거나 같은 자연수임으로 1000 * 100 임으로 10^5 안으로 들어온다. 비용에 대해서 얻을 수 있는 고객의 수를 dp로 이용해 풀어주었다. 처음에는 고객을 얻기 위해 지불해야하는 최소의 비용을 구하려고 했다가 문제에서 호텔의 고객을 적어도 c명 늘여야했기 때문에 dp를 수행하여 c에서 어느정도까지의 범위를 탐색하야하는지 정하기 어렵기때문에 비용에 대해서 얻을 수 있는 고객의 수를 dp로 하고 dp안에 담겨 있는 값이 c이상이 된다면 멈추는 것으로 답을 구했다. 조건문을 통해 i-cost[i] < 1보다 작아 질수가 있기 때문에 continue 해주고 dp[i] <= dp[i-cost[i]] + value[i] 이면 dp[i]값을 update해주었다. 시간제한 2초이고 메모리제한 128MB안에 들어간다.

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> c >> n;
    for (int i = 1; i <= n; i++)
    {
        int c, v;
        cin >> c >> v;
        cost[i] = c;
        value[i] = v;
    }

    // dfs(0,0);

    // for(int i = 1; i<=n ; i++)
    // {
    //     for(int w= 0 ; w<=c ; w++)
    //     {
    //         dp[i][w] = dp[i-1][w];
    //         if(w<=cost[i])
    //         {

    //         }
    //     }
    // }

    // dp[i] i에 cost넣고 dp[i] 값에  고객수?
    for(int i = 1; i<=n ; i++)
    {
        dp[cost[i]] = max(dp[cost[i]], value[i]) ;
    }


    for (int i = 1; i <= 100000; i++) 
    {
        for (int j = 1; j <= n; j++)
        {
            if (i - cost[j] < 1)
                continue;
            if (dp[i] <= dp[i - cost[j]] + value[j])
            {
                dp[i] = dp[i-cost[j]] + value[j];
            }
        }
    }

    //cout << dp[8] <<"\n";

    // for(int i = 1; i<= 181 ;i++)
    // {
    //     cout << dp[i] <<" ";
    // }
    // cout <<"\n";


    for(int i = 1; i<= 100000; i++)
    {
        if(dp[i] >= c)
        {
            cout << i <<"\n";
            break;
        }
    }

    // cout << result <<"\n";
}