[Gold V] 호텔 - 1106 (DP)

풀이 방법

필요한 고객 수를 만족하는 도시들 중 최소 비용을 찾는 문제라서 사용해야 할 알고리즘 중 이분 탐색을 생각했었다. 그렇다면 이분탐색을 할 대상은 비용이 되는데, 이분탐색을 위한 각 도시들 중 비용의 최소와 최대를 구해야 한다. 그러나, 동일한 도시의 고객이 여러번 올 수도 있기에 해당 알고리즘으로는 해결이 안되었다.

도대체 뭐지? 하고 찾아봤더니, DP 알고리즘이었다.

1. dp 알고리즘을 사용할 최댓값을 설정한 배열을 생성한다. 배열의 길이는 필요한 고객수 + 100 이다. 왜냐하면 주어진 문제에서 가 도시마다 올 수 있는 비용과 고객 값은 100 이하 자연수임과 동시에 필요한 고객수를 한 번 초과하더라도 비용이 최소가 될 수 있기 때문이다. 그러므로 최악의 경우, 필요한 고객수 + 100명이 최소 비용이 될 수도 있다는 것이다.

2. 각 도시를 탐색하며 해당 도시의 고객 수 인덱스에서의 dp값의 최솟값을 구한다. (해당 도시 고객이 오기 전 인덱스에서 해당 도시 고객을 추가했을 경우(dp[i-man])와 기존에 저장된 해당 dp인덱스의 값 (dp[i]) 중 최솟값 초기화)

3. 최종적으로, 최소 비용이 필요한 고객수보다 많았을 경우에도 생길 수 있으니까 dp 인덱스에서 필요한 고객 수 이상인 값들 중 가장 최솟값을 출력한다.(min(dp[customer_cnt:]))

customer_cnt, city_cnt = map(int,input().split()) # 필요한 고객 수, 도시 수

city_arr = []
for city in range(city_cnt):
    city_arr.append(list(map(int,input().split())))
dp = [10**9] * (customer_cnt + 100) # 고객과 비용은 최대 100 이하
dp[0] = 0
for cost, man in city_arr:
    for i in range(man, customer_cnt + 100):
        dp[i] = min(dp[i-man] + cost, dp[i])
print(min(dp[customer_cnt:]))