백준 1106 호텔 파이썬 풀이

난이도 : 골드5

풀이일 : 2404055

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

1106번: 호텔

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

풀이코드

import sys

C, N = map(int, sys.stdin.readline().split())
ad = []
# 비용 정보 없음, 고객의 수 최대 100명
dp = [int(1e9)] * (C + 100)
dp[0] = 0  # 0 초기화

for _ in range(N):
    cost, people = map(int, sys.stdin.readline().split())
    ad.append([cost, people])

for cost, people in ad:
    for i in range(people, C + 100):
        # dp[i - people] : i - people 명을 모을 때 최소비용
        dp[i] = min(dp[i], dp[i - people] + cost)

print(min(dp[C:]))

• ad : 비용, 고객 수 정보 기록할 배열입니다.
• dp : 비용 정보가 없으므로 충분히 큰 수 int(1e9)로 초기값을 설정해줍니다. 문제를 읽고 비용도 100이 최대인가 싶었는데 그렇게 설정하면 틀리더라고요. 고객 수는 최대 100명으로 나와있기 때문에 dp는 C + 100으로 설정해줍니다.
• dp[0] = 0 : 아무 광고도 하지 않은 경우의 값을 재할당 해줍니다.

 

입력 받기

for _ in range(N):
    cost, people = map(int, sys.stdin.readline().split())
    ad.append([cost, people])

• cost, people 정보를 ad에 추가해줍니다.

 

dp 계산

for cost, people in ad:
    for i in range(people, C + 100):
        # dp[i - people] : i - people 명을 모을 때 최소비용
        dp[i] = min(dp[i], dp[i - people] + cost)

print(min(dp[C:]))

• ad 배열에 있는 cost, people 정보를 가지고, 반복문을 수행합니다.
• people 부터 C + 100인 배열의 끝까지 dp[i] 정보를 재할당 해줍니다.
• dp[i]는 현재 저장되어있는 값(dp[i])과 i - people 명을 모을때의 최소 비용에 현재 비용을 더한 값(dp[i - people] + cost) 중 작은 것으로 저장합니다.
• 최종적으로 C 명 이상을 모을 수 있는 경우 중, 가장 작은 값을 출력합니다.

---

느낀점

• dp문제를 풀어오지 않아서 그런지 간단한 로직인데도 떠올리고 코드로 옮기고 하는 과정이 오래 걸렸습니다. 익숙하지 않은 유형의 문제를 골라서 풀기로 하길 잘한 것 같아요.
• 비슷한 유형의 dp, 배낭 문제들을 풀어보며 익숙해지도록 해야겠습니다.