1106. [Python]호텔

1. 문제

 

https://www.acmicpc.net/problem/1106

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 배낭 문제
• 다이나믹 프로그래밍

 

3. 파이썬 코드

 

import sys

input = sys.stdin.readline

C, N = map(int,input().split())

dp = [10**9] * (C+101)

moneys = []
# 초기 들어온 값들을 dp 에 사람수와 비용으로 초기값 선언
for _ in range(N):
    cost, people = map(int,input().split())
    moneys.append((cost,people))
    dp[people] = min(cost,dp[people])
# 이후 C 값은 최대 1000 보다 작고 비용은 100 값보다 작거나 같은 자연수 이므로 범위를 최대 1101로 설정
for i in range(1,C+101):
    # 현재 비용에서 들어오는 비용 값을 뺀값이 양수면 해당 비용에 대해서 dp 값 갱신해줌
    for c, p in moneys:
        if i - p >= 1:
            dp[i] = min(dp[i-p]+dp[p],dp[i])
# 고객이 최소 C 명 이상이기 때문에 이후 값들중 최소값 탐색
print(min(dp[C:]))

 

4. 문제를 풀고난 후 생각

 

• 범위를 처음 살펴보고 값이 크지 않은 것을 알았고, C의 값이 1000 보다 작은 것을 고려한 후 최대 100원이 더해진 1100 까지가 나올 수 있는 범위의 한계 인 것을 파악했다.
• 이후 그 사람을 모으기 위한 값들에 대해서 dp 리스트를 갱신해주는 방법으로 문제를 풀었다.
• 문제에서 요구한 조건은 최소 C 명 이상이 될때 최소 비용은 얼마인지 였으므로 출력단에서 C 부터 끝 범위까지 했을때 최소비용을 찾아서 출력해주면 된다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 배낭 문제