[Python] 백준 1106 - 호텔 문제 풀이

Overview

BOJ 1106번 호텔 Python 문제 풀이
분류: Dynamic Programming (동적계획법)

---

문제 페이지

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

---

풀이 코드 1

from sys import stdin, maxsize
input = lambda: stdin.readline().rstrip()


if __name__ == "__main__":
    c, n = map(int, input().split())
    promotions = [tuple(map(int, input().split())) for _ in range(n)]

    promotions.sort()
    dp = [0] + [1000000] * (c + 100)
    res = maxsize
    for cost, client in promotions:
        for i in range(client, len(dp)):
            dp[i] = min(dp[i - client] + cost, dp[i])
            if i >= c:
                res = min(dp[i], res)
    print(res)

다이나믹 프로그래밍을 이용하여 dp에 고객 i명이 늘어날 때 최소 비용을 저장한다. 그리고 적어도 c명의 고객이 늘어나기 위한 최소 비용을 구하기 위해 dp의 인덱스 c 이후 값 중에서 최소값을 구한다.

---

풀이 코드 2

from sys import stdin
input = lambda: stdin.readline().rstrip()


MAX = 100_001


if __name__ == "__main__":
    C, N = map(int, input().split())
    costs = list(tuple(map(int, input().split())) for _ in range(N))

    dp = [0] + [MAX] * C
    for i in range(C):
        for cost, client in costs:
            if i + client < C:
                # 늘어나는 고객 수에 따른 최소 비용 비교
                dp[i + client] = min(dp[i + client], dp[i] + cost)
            elif i + client >= C:
                # 늘어나는 고객 수가 C이상일 때 최소 비용 비교
                dp[C] = min(dp[C], dp[i] + cost)

    print(dp[C])

1번 풀이와 비슷한 풀이이다.