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

Overview

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

문제 페이지

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

풀이 코드

from sys import stdin, maxsize


def main():
    def input():
        return stdin.readline().rstrip()

    c, n = map(int, input().split())
    promotions = sorted([tuple(map(int, input().split())) for _ in range(n)])

    dp = [0] + [1000000] * (c + 100)
    res = 1000000
    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)


if __name__ == "__main__":
    main()

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