[백준/python] 1106번 호텔

1. 문제

 

이 문제는 호텔의 홍보 비용에 따른 고객 수 증가 정보를 가지고

호텔의 고객을 c명 이상 늘이기 위해 투자해야 하는 돈의 최솟값을 구하는 문제이다.

 

2. 풀이

[접근 1 - dfs] 시간초과

처음에는 dfs를 활용하여 재귀 형태로 모든 경우의 수를 확인하도록 했다.

모든 방법을 확인하다가 고객 수가 c 이상이 될 경우 최솟값을 갱신하고 return하는 형태이다.

답을 찾는 데는 무리가 없었으나 시간초과가 떠버렸다.

이에 시간을 줄일 수 있는 다른 방법을 고민했다.

 

[접근 2- dp]

목표 고객 증가 수인 c에다가 한 번의 투자로 늘어날 수 있는 최댓값인 100을 더해서 dp테이블을 만들었다.

혹시 c보다 c+1이 더 비용이 적게 들 수도 있기 때문이다.

dp 테이블은 모두 큰 수로 초기화해두고 반복문을 돌렸다.

홍보 비용 및 고객 정보에 대하여 반복문을 실행하여 최솟값을 갱신하였다.

마지막에는 dp테이블에서 c보다 큰 인덱스들에 대해서 최솟값을 찾는 방식으로 문제를 해결하였다.

이 때 시간초과가 되지 않고 통과할 수 있었다.

 

 

3. 코드

[접근 1]

import sys
input = sys.stdin.readline

def dfs(cost, person):
    global min_cost
    #만약 고객 수가 목표한 값에 도달하면
    if person >= c:
        #최소 비용 갱신
        min_cost = min(min_cost, cost)
        return
    #모든 정보에 대해 cost, person 추가 후 재귀 함수 실행
    for i in range(n):
        cost += arr[i][0]
        person += arr[i][1]
        dfs(cost, person)
        cost -= arr[i][0]
        person -= arr[i][1]
        
#입력 받기
c, n = map(int, input().split())
arr = [tuple(map(int, input().split())) for _ in range(n)]
min_cost = float("inf") #최소비용 초기화

dfs(0, 0)
print(min_cost)

 

[접근 2]

import sys
input = sys.stdin.readline

c, n = map(int, input().split())
arr = [tuple(map(int, input().split())) for _ in range(n)]
dp = [1e7 for _ in range(c+100)] #dp 테이블 초기화
dp[0] = 0

#비용, 고객 정보에 대하여 해당 고객수까지의 최소 비용 갱신
for a, b in arr:
    for i in range(b, c+100):
        dp[i] = min(dp[i-b]+a, dp[i])

print(min(dp[c:]))

 

4. 결과

 

문제를 풀다가 시간초과가 뜰 때는 다른 알고리즘을 사용하는 것이 좋을 때가 있다.

그걸 잘 구분해서 시간 초과 에러를 해결해봐야겠다.