[BJ-G4] C++ : 1106번 호텔

지난 알고리즘 풀이 이후로 블로그로 기록하지는 않았지만, 꾸준히 하루에 최소 한 문제씩, 목표 3문제씩 코드카타를 해왔다. 오늘 풀이할 문제는 백준 Gold4의 "호텔"이라는 문제다. 

문제 링크: https://www.acmicpc.net/problem/1106

문제 분석

Input: 

• C : 늘려야 할 고객의 수
• N : 도시의 개수
• (비용 , 고객의 수) * N : 각 도시에서의 홍보비 별 구할 수 있는 고객의 수

Output: 

• result: 홍보 비용으로 얻을 수 있는 고객의 수

문제 풀이

#include <iostream>
#include <vector>
#include <algorithm>

constexpr int INF = 1e9; //max Int

using namespace std;

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

    int target, cityCount;
    cin >> target >> cityCount;

    /*inputs*/
    vector<pair<int, int>> cities(cityCount); //cost, cumtomers
    for (int i = 0; i < cityCount; i++) {
        int cost, customers;
        cin >> cost >> customers;
        cities[i] = {cost, customers};
    }

    /*
    * minCost per targetSize
    * arrSize : 도시 홍보 단위가 클 것을 위한 여유공간 확보
    * INF : 최대 비용
    */
    vector<int> dp(target + 101, INF); 
    dp[0] = 0; //when targetSize = 0

    /*
    * 1회차 : 첫 도시에서의 비용으로 dp 초기화.
    * 2회차 이후 : 다음 도시에서 특정 인원일 때의 비용이 더 싸다면 대체하기
    */
    for (const auto& city : cities) {
        int cost = city.first;
        int customers = city.second;
        
        /*
        * 1회차일 때는 반드시 dp[j - customers] + cost가 더 쌈.
        * j - customers인 이유: 
        * targetSize가 j일 때, 마지막 홍보비를 특정 도시로 설정하기 위함.
        */
        for (int j = customers; j < dp.size(); j++) {
            dp[j] = min(dp[j], dp[j - customers] + cost);
        }
    }

    /*
    * 최소한 target명의 고객을 확보할 수 있는 최솟값을 찾기
    * 이때, 정확히 target명을 맞추는 것보다 오히려 더 많은 이에게 홍보하는 것이 
    * 가격이 더 쌀 수 있다는 사실을 고려해야 함.
    */ 
    int result = *min_element(dp.begin() + target, dp.end());
    cout << result << '\n';
}

느낀 점

 

오늘 풀어본 문제는 동적 프로그래밍이 필요한 문제였다. 처음에는 각 도시의 홍보 효율을 계산해, 효율이 높은 도시 순으로 정렬하여 해결하려 했다. 그러나 마지막에 도달할 때쯤, 최고 효율의 도시 한 단위를 선택하는 것과, 효율은 낮더라도 절대 비용이 적은 도시를 선택하는 사이에서 조건을 맞추는 데 어려움을 겪었다. 결국 코드를 모두 지우고, 문제의 힌트로 주어진 알고리즘 테마를 보고 나서야 동적 프로그래밍으로 접근해야 한다는 점을 깨달았다.

이번 문제를 통해 아직 동적 프로그래밍에 대한 이해가 부족하다는 점을 실감하게 되었다. 그래서 이번 주는 동적 프로그래밍을 집중적으로 공부하며 관련 문제들을 더 풀어봐야겠다고 다짐했다.

오랜만에 블로그 글을 쓰기 위해 지난달의 글을 다시 보니, 한 달 사이에도 실력이 향상되었음을 느낄 수 있었다. 이번 문제는 해결하는 데 다소 시간이 걸렸지만, 매주 한 번씩 고난도 알고리즘 문제를 도전하고 기록하며 앞으로도 실력을 꾸준히 쌓아가고 싶다.