[골드 V] 1106번. 호텔

 문제 

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

1106번: 호텔

 사용 언어 

Python3

 풀이 과정 

처음에는 어제 동전 1 푸는 법을 공부했다고 그래도 거의 비슷하게 아래와 같이 풀었다.

# 원하는 만큼 고객을 늘리기 위한 투자 비용의 최솟값
from sys import stdin

input = stdin.readline
goal, cities = map(int, input().split())
dp = [0] * (goal + 1)
costDict = {}
for i in range(cities):
    cost, customer = map(int, input().split())
    costDict[customer] = cost
customerList = costDict.keys()

for j in range(1, goal + 1): # 1 ~ 10명
    minCost = float("inf")
    for k in customerList: # 3, 2, 1명
        if k <= j:
            minCost = min(minCost, dp[j-k] + costDict[k])
    dp[j] = minCost
    
# dp = [0, 3, 2, 1, 4, 3, 2, 5, 4, 3, 6]

그런데 결과값이 다른게 아닌가..?! 문제를 다시 읽으니 "적어도" 목표만큼의 고객을 늘이기 위한 투자 비용의 최솟값을 구하는 거였다. 하......문제.....잘보기로 해놓고.....😡 또 이런 실수를 반복하다니.

어쨌든 그래서 정확한 목표 고객을 넘겨서 최솟값이 나오는 경우를 위해 range를 2000까지나 늘려봤는데

예시 출력값은 모두 맞지만 제출만 하면 1초컷으로 뜨던 틀렸습니다...

 

결국 위 로직은 버리고 다른 블로그 참고해서 비슷한듯 다르게 짰는데 저 코드 왜 틀린건지 너무 궁금하다...

예시 결괏값이 다 맞고 다른 예를 내 뇌로 만드는게 더 시간이 오래걸릴거같은;; 느낌이라 일단은 넘어갓

힙겹게 본 맞았습니다!!
다른 두 개의 맞았습니다 버전은 아래에서 설명하겠다.

어쨌든 이 문제의 포인트는 "적어도"에 집중하는 것, 그리고 역시 DP 문제답게 점화식을 세우는 것이었다.

 제출 답안 

from sys import stdin

input = stdin.readline
goal, cities = map(int, input().split())
dp = [float("inf")] * (goal + 100)
dp[0] = 0
info = []
for i in range(cities):
    info.append(list(map(int, input().split())))

for cost, customer in info:
    for i in range(customer, goal + 100):
        dp[i] = min(dp[i-customer] + cost, dp[i])

print(min(dp[goal:]))

 다른 사람 답안 

나는 문제에서 비용으로 얻을 수 있는 고객의 수가 최대 100명이었기 때문에 그냥 무조건 goal에 100명을 더해줬는데,
당연히 예시에서 주어진 가장 큰 수를 더하면 더 최적의 효율일 것이다.

그걸 반영한게 아래의 코드였다.

import sys
input = sys.stdin.readline

def main():
    c, n= map(int, input().rstrip().split())
    li = [list(map(int, input().rstrip().split())) for _ in range(n)]
    m = c + max(list(map(lambda x: x[1], li)))
    dp = [0] + [sys.maxsize] * m

    for cost, customer in li:
        for cur_customer in range(customer, m+1):
            dp[cur_customer] = min(dp[cur_customer], dp[cur_customer - customer] + cost)
    print(min(dp[c:]))
if __name__ == '__main__':
    main()

출처: 백준 채점 현황

 

그런데 내가 제일 궁금하고 신기했던건, 내 코드에 그대로 반영했는데 오히려 80ms에서 84ms로 오르길래

읭스러워서 혹시 몰라  main( )  함수로 감싸줬더니 76ms로 줄어들었다는거다.

 

이게  if __name__ == '__main__' 의 효과인지 아님 전역으로 실행되던게 지역으로 실행돼서인지가 궁금해서

if문 줄만 빼고 실행해봤는데 똑같이 76ms가 나왔다. 함수로 감싸주면서 실행 범위가 달라진 영향이었던 것!