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. 결과
문제를 풀다가 시간초과가 뜰 때는 다른 알고리즘을 사용하는 것이 좋을 때가 있다.
그걸 잘 구분해서 시간 초과 에러를 해결해봐야겠다.
'Programming > CodingTest' 카테고리의 다른 글
[백준/python] 3273번 두 수의 합 (0) | 2024.05.10 |
---|---|
[백준/python] 9465번 스티커 (0) | 2024.05.09 |
[백준/python]1259번 팰린드롬수 (0) | 2024.05.05 |
[백준/python] 3980번 선발 명단 (0) | 2024.05.04 |
[알고리즘] 백트래킹 Backtracking (0) | 2024.05.03 |