백준 1106: 호텔

관련 링크 : https://www.acmicpc.net/problem/1106

백준 1106 : 호텔

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

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

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

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

입력

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

12 2
3 5
1 1

출력

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

8

풀이

이전에 1103번 문제에서 Dynamic Programming을 처음 접한 이후로 두 번째로 풀어본 DP 문제이다. 딱히 알고리즘을 공부하고 문제를 푸는게 아니라서, DP의 정의만 보고 이 문제를 어떻게 접근해야 할지 막막했다. 그래서 처음 시도해 본 방식은

1. 도시 홍보 정보들의 리스트를 효율이 좋은 순서, 동일 효율은 비용이 큰 순으로 정렬
2. 홍보 목적인 고객 수 C를 초과해도 되므로, 가장 효율이 좋은 정보로만 홍보 했을 때와 가장 효율이 좋은 정보로 C를 초과하지 않게 홍보 후 남은 것들을 그 다음 효율의 정보들로 홍보했을 때를 비교

def getInput():
    C, N = map(int, input().strip().split())
    infos = [list(map(int, input().strip().split())) for _ in range(N)]
    return C, infos

def solution(remain, infos):
    cost, customer = infos.pop()
    if remain%customer: #도시의 정보를 이용해 최대한 홍보 후 남은 고객 수
        if infos: #목표 고객을 달성하지 못했고, 남은 정보가 있는 경우
            return (remain//customer) * cost + min(solution(remain%customer, infos), cost)
        else: #남은 정보가 없는 경우
            return (remain//customer + 1) * cost
    else: #목표 고객을 달성한 경우
        return (remain//customer) * cost
    
if __name__ == "__main__":
    C, infos = getInput()
    infos = sorted(sorted(infos, key=lambda x: x[1]), key=lambda x: x[1]/x[0])
    #먼저 비용이 작은 순으로 정렬 후, 효율 낮은 순으로 정렬. 앞서 말한 1번을 위함
    print(solution(C, infos))

아쉽게도 틀렸는데, 문제를 반례를 못 찾았다. 그래서 DP를 이용한 다른 사람들의 풀이를 참고해서 다음과 같이 풀었다.

import sys

sys.setrecursionlimit(10000)

def dp(C, cur, infos):
    if costs[cur] >= C:
        #목표 고객 수 C를 넘었을때 비용 cur을 기록
        answers.append(cur)
        return
    for cost, customer in infos:
        if costs[cur] + customer > costs[cur + cost]:
            #Memoization을 위한 costs에서 새로 계산한 값이 기존 값보다 큰 경우만 갱신
            costs[cur + cost] = costs[cur]+customer     
            dp(C, cur+cost, infos)

if __name__=="__main__":
    C, infos = getInput()
    costs =  [0] * 100*1000 + [0] #costs[비용] = 고객 수
    #길이는 Worst Case인 C=1000, 정보는 비용 100으로 1명에게 홍보가능 한 경우
    answers = []
    dp(C, 0, infos)
    print(min(answers)) #기록된 비용중 가장 낮은 값을 출력

가장 기초적인 DP 문제라고 하는데, 쉽지 않았다.