Skip to main content

1106 - 호텔

info
  • 문제 보기: 1106 - 호텔
  • 소요 시간: null (기억안남 이슈)
  • 풀이 언어: python
  • 체감 난이도: 4️⃣
  • 리뷰 횟수: ✅

풀이 키워드​

스포주의

DP


풀이 코드​

info
  • 메모리: 33240 KB
  • 시간: 2532 ms
import sys
from math import ceil
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

c, n = 0, 0
data, memo = [], []
inf = 1987654321

def dp(city, remain):
    global memo
    
    if city >= n and remain > 0:
        return inf
    
    if remain <= 0:
        return 0
    
    if memo[city][remain] > 0:
        return memo[city][remain]
    
    mn = inf
    KMAX = ceil(remain / data[city][1])
    
    for k in range(KMAX+1):
        new_remain = remain - data[city][1] * k
        ret = dp(city+1, new_remain) + data[city][0] * k
        if ret < mn: mn = ret
        
    memo[city][remain] = mn
    return mn
    

def solution():
    global c, n, data, memo
    
    c, n = map(int, input().split())
    data = [0] * n
    for i in range(n):
        pay, people = map(int, input().split())
        data[i] = (pay, people)
        
    memo = [[0] * (c+101) for _ in range(n)]
    
    # c를 넘어가더라도 더 가성비있을 수 있으므로 c+100까지 탐색
    mn = inf
    for i in range(101):
        ret = dp(0, c+i)
        if ret < mn: mn = ret # min( dp(0, c) ~ dp(0, c+100) )
    print(mn)
    
if __name__ == '__main__':
    solution()

풀이 해설​

dp를 101번 돌려서 무식하게 해결했다.

자세한 설명은 생략한다.

고객은 다다익선​

둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.

# c를 넘어가더라도 더 가성비있을 수 있으므로 c+100까지 탐색
mn = inf
for i in range(101):
    ret = dp(0, c+i)
    if ret < mn: mn = ret # min( dp(0, c) ~ dp(0, c+100) )

각 도시별로 얻을 수 있는 고객의 단위가 100명 이하이므로

최소의 경우는 1명씩, 최대의 경우는 100명씩 얻을 수 있다.

하지만 고객 수가 목표치를 넘치든 말든 구하고자 하는 값은 최소 투자 비용이므로,

목표 고객 증가 수 c에서 c+100 까지 탐색해보아야 한다고 생각했다.

근데 잘 생각해보니까 c+99까지 탐색하면 그만이긴 하다. 왜냐하면 c-1 에서 +1을 선택할지 +100을 선택할지 고민하는 것이므로. (하지만 c+99로 채점했을때 결과가 더 좋지 않아서 굳이 수정은 안하겠음)


나머지는 그냥 남은 목표 고객치 remain에 대해서 dp를 수행하는 로직이다.