문제 설명
•
최소 비용으로 적어도 C명의 고객을 확보하는 방법을 구하는 문제
예제 입력/출력
•
입력1
12 2
3 5
1 1
Plain Text
복사
•
출력1
8
Plain Text
복사
제약 조건
•
•
•
홍보 비용, 얻을 수 있는 고객의 수
문제 풀이
접근1 브루트 포스 (완전 탐색) -
접근2 그리디
접근3 2차원 DP (Bottom-Up) -
접근4 2차원 DP (Top-Down) -
•
접근5 1차원 DP (Bottom-Up) -
◦
고객의 c명 이상 유치하기 위한 최소 비용을 구하는 방법
▪
핵심 아이디어: 각 도시를 여러 번 사용할 수 있으므로, 모든 고객 수(c)에 대해 여러 번 갱신
◦
DP 테이블 정의
▪
dp[c]: 고객을 c명 이상 유치하기 위한 최소 비용
•
◦
DP 관계식
for c in range(1, C + 100):
for n in range(1, N + 1):
if c - customer[n] >= 0:
dp[c] = min(dp[c], dp[c - customer[n]] + cost[n])
Python
복사
▪
C + 100 크기로 설정한 이유는 정확히 C명이 아니라 그 이상도 가능하기 때문
•
한 도시에서 한번 홍보했을 때 얻을 수 있는 고객의 수
◦
초기값 처리
▪
dp[0] = 0
•
고객 0명을 유치하는 데 드는 비용은 0
풀이 코드
2차원 DP (Bottom-Up) -
2차원 DP (Top-Down) -
•
1차원 DP (Bottom-Up) -
◦
세 개의 코드를 비교했을 때, 공간 복잡도와 시간 복잡도 측면에서 성능이 가장 우수
import sys
INF = int(1e9)
input = sys.stdin.readline
mii = lambda: map(int, input().split())
# 입력 처리
C, N = mii()
cost, customer = [0], [0]
for _ in range(N):
ct, cs = mii()
cost.append(ct)
customer.append(cs)
# DP 테이블 초기화
MAX_CUSTOMERS = C + 100
dp = [INF] * MAX_CUSTOMERS + 1
dp[0] = 0
# Bottom-Up DP 수행
for c in range(1, MAX_CUSTOMERS):
for n in range(1, N + 1):
if c - customer[n] >= 0:
dp[c] = min(dp[c], dp[c - customer[n]] + cost[n])
# C보다 큰 dp값 중 최소값 출력
print(min(dp[C:]))
Python
복사
