[백준] #1106 호텔(python)

📌문제

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

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

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

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

입력

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

출력

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

예제 입력1

12 2
3 5
1 1

예제 출력1

8

예제 입력2

10 3
3 1
2 2
1 3

예제 출력2

4

예제 입력3

10 10
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

예제 출력3

10

백준 1106번 문제

💡Idea

형택이가 고객을 C명 늘리기 위해서 최소한 얼마를 써야하는지를 구하는 문제입니다.

이 것을 뒤집어서 생각해보면, 형택이가 투자하는 돈에 따라 각각 최대로 늘릴 수 있는 고객의 명수를 구하는 것으로도 문제를 해결해 볼 수 있습니다.

형택이가 투자하는 돈을 1원부터 시작하여 각 금액에 따라 최대로 늘릴 수 있는 고객의 명수를 DP를 통해 구하면서, 목표하는 고객의 수 C명이 나올 때의 금액을 찾아 문제를 풀어봅시다!

💻코드

• ⏰ 시간 : 164 ms / 메모리 : 42620 KB

import sys
input = sys.stdin.readline
C, N = map(int, input().split())
cities = [] 

for _ in range(N):
    cities.append(list(map(int, input().split())))

dp = {0: 0} 
now = 1

while True:
    dp[now] = 0 # 새 금액 딕셔너리에 추가
    for cost, customer in cities: 
        if (now - cost) in dp:
            dp[now] = max(dp[now], dp[now - cost] + customer)
    if dp[now] >= C: break # 현재 금액으로 늘릴 수 있는 최대고객수가 C 이상이면 종료
    now += 1 # 금액 1 증가
print(now)

📝코드 설명

변수

• cities : 각 도시의 [홍보할 때 드는 비용, 그 비용으로 얻을 수 있는 고객 수]를 저장하는 리스트입니다. 인덱스가 각 도시의 번호가 됩니다.

• dp : 금액 별 최대 고객 수를 저장하는 딕셔너리로, key가 금액, value가 최대 고객 수입니다.
  최대 금액의 범위가 주어지지 않았기 때문에 딕셔너리를 사용하여 계속해서 금액을 추가해줄 수 있도록 하였습니다.

• now : 현재 금액

금액을 1부터 시작하여 1씩 늘려가면서 각 금액 별 최대 고객 수를 찾아 저장해줍니다.

매 금액 별로, 아래의 두 가지 값을 비교하여 더 큰 값을 dp[now]에 넣어줍니다.(두 가지 값은 각각 고객의 수를 의미하며, 최대 고객 수를 넣어줘야 하므로 더 큰 값을 넣어줍니다.)

1. 현재 dp[now] 값 : 현재 now의 금액으로 늘릴 수 있는 고객의 수(최대인지는 아직 모름)
2. dp[now - cost] + customer : 해당 도시에서 cost의 금액을 들여서 customer만큼의 고객을 늘린 상황으로, now - cost로 늘릴 수 있었던 최대 고객의 수와 새롭게 늘린 고객의수 customer를 더한 값

그리고 최대 고객의 수가 목표했던 C를 넘어서면 반복문을 종료하고 그 때의 금액을 출력해주면 됩니다.