백준: 1106 호텔

문제

1106번: 호텔

 

문제 풀이

 적어도 유치해야 하는 고객 수 C명과 도시의 개수 N이 주어진다. 이때 각 도시에는 홍보비용과 그 비용으로 유치할 수 있는 고객에 대한 정보가 제공된다. 이때, 최소 비용으로 적어도 C명의 고객의 수를 유치하는 경우를 반환하는 문제이다.

 

 문제를 풀기 위해서는 메모이제이션을 통해, 다음과 같이 점화식을 세우면 해결할 수 있다. `dp[N명의 고객을 유치하는데 드는 비용] = min(dp[N명의 고객을 유치하는데 드는 비용], dp[N명의 고객을 유치하는데 드는 비용 - 현재 방문한 도시의 유치 가능한 인원수) + cost)`

 

 이를 다시 풀어서 설명한다면, 현재 유치 가능한 고객과 이전에 메모이제이션을 통해 유치한 값 중 최솟값을 찾아 다시 기록하는 방식을 취하는 방식을 통해 원하는 값을 찾을 수 있다. 문제를 푸는 데 있어 주의할 점은 최초에 제출할 때는 C가 12인 경우 `dp[-1]`이 답이 되므로, 당연히 그런 식으로 생각하고 제출하였지만 오답이었다. 이는, 적어도 C명을 늘려야 하기에 C의 최댓값은 100을 고려하여 DP를 계산해주어야 하기 때문이다.

 

코드

from sys import stdin, maxsize


if __name__ == '__main__':
    # 확보해야할 고객, 도시의 수
    C, N = map(int, stdin.readline().split())
    # 광고 정보
    ad = [list(map(int, stdin.readline().split())) for _ in range(N)]
    # 적어도 C명을 늘려야 하기에, 고객의 수 최대 값을 더해 줄 필요가 있음
    dp = [0] + [maxsize] * (C + 100)

    for cost, customer in ad:
        for cur_customer in range(customer, C + 101):
            dp[cur_customer] = min(dp[cur_customer], dp[cur_customer - customer] + cost)

    print(min(dp[C:C + 101]))