1106번: 호텔
첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때
www.acmicpc.net
문제
세계적인 호텔인 형택 호텔의 사장인 김형택은 이번에 수입을 조금 늘리기 위해서 홍보를 하려고 한다.
형택이가 홍보를 할 수 있는 도시가 주어지고, 각 도시별로 홍보하는데 드는 비용과, 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보가 있다.
예를 들어, “어떤 도시에서 9원을 들여서 홍보하면 3명의 고객이 늘어난다.”와 같은 정보이다. 이때, 이러한 정보에 나타난 돈에 정수배 만큼을 투자할 수 있다. 즉, 9원을 들여서 3명의 고객, 18원을 들여서 6명의 고객, 27원을 들여서 9명의 고객을 늘어나게 할 수 있지만, 3원을 들여서 홍보해서 1명의 고객, 12원을 들여서 4명의 고객을 늘어나게 할 수는 없다.
각 도시에는 무한 명의 잠재적인 고객이 있다. 이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
코드
import sys
input = sys.stdin.readline
c, n = map(int, input().split())
info = []
dp = [int(1e9)] * (c+101) # 고객 수별 최소 비용 저장
dp[0] = 0
for _ in range(n):
info.append(list(map(int, input().split()))) # 비용, 고객 수
for cost, num in info:
for i in range(num, c+101):
dp[i] = min(dp[i], dp[i-num]+cost)
print(min(dp[c:]))
dp배열에 고객 수별 최소 비용을 저장한다. 예를 들어 dp[5]에는 5명의 고객을 유치할 때 드는 최소 비용이 저장되는 것이다.
처음에는 dp 배열의 크기를 c+101이 아닌 1001로 잡아두고 반복문의 범위도 1001까지 했었는데 틀렸었다. 홍보할 때 대는 비용이 최대 100이라고 했으니 배열의 크기는 c+101로만 잡아도 된다. 그 이상 잡고 min(dp[c:])를 하면 비용이 더 작아지는 경우가 발생하는 것 같다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 2294번 동전 2 (0) | 2023.05.30 |
---|---|
[Python/파이썬] 백준 2293번 동전 1 (0) | 2023.05.29 |
[Python/파이썬] 백준 22871번 징검다리 건너기 (large) (0) | 2023.04.30 |
[Python/파이썬] 백준 2624번 동전 바꿔주기 (0) | 2023.04.15 |
[Python/파이썬] 백준 5557번 1학년 (0) | 2023.04.15 |