백준 1106 - 호텔

문제 설명

제한사항 및 입출력

풀이

문제 요약은 다음과 같다. 각 도시에서 광고에 cost원을 쓰면 people명의 고객을 얻는다. 최소 C명 이상의 고객을 모으기 위해 써야 하는 최소 비용을 구하라. 같은 도시는 여러 번 사용할 수 있다.

전형적인 배낭 문제이다. 핵심은 “같은 아이템(도시)을 무한히 쓸 수 있음” -> 완전 배낭 형태이다. 또한 “정확히 C명”이 아니라 “C명 이상”을 만족하면 된다.

직관적으로 봤을 때 그리디로도 접근할 수 있을 것 같이 생겼지만 초과분의 존재 때문에 최적해를 보장할 수 없다.

 

dp테이블의 정의는 다음과 같이 내렸다.

dp[i] = i명을 모으는 데 드는 최소 비용

또한 초과해서 모아도 되기 때문에 한 번에 모을 수 있는 최대 비용을 여유분으로 넉넉하게 지정해주었다.

내 코드

import sys
input = sys.stdin.readline
mis = lambda: map(int, input().split())
INF = float('inf')

# c명 늘리기 위해 투자해야하는 돈의 최솟값
c, n = mis()
arr = [[*mis()] for _ in range(n)]

# dp[i] = i명 모으는데 드는 최소 비용
limit = c + max(arr, key= lambda x:x[1])[1]
dp = [INF] * (limit+1)
dp[0] = 0

for i, j in arr:
    for x in range(j, limit+1):
        dp[x] = min(dp[x], dp[x-j] + i)

print(min(dp[c:]))

같은 도시를 여러 번 사용할 수 있기 때문에 도시를 앞에서부터 순회하며 dp 테이블의 상태를 전이해주었다.

각 도시에 대해 모든 dp 테이블을 순회하며 앞에서 해당 도시를 사용한 경우와 이미 채워진 값을 비교하여 더 작은 값으로 갱신하여 통과했다.

고찰

이런 배낭 문제는 각 아이템을 몇 번이나 반복해서 사용할 수 있는지에 대한 여부가 굉장히 중요하다. 자주 나오는 선택 가능 횟수를 분류해보자면 다음 두 가지가 있고, dp의 정의는 공통적으로 다음과 같다.

1차원 dp: dp[w] = 용량 w에서의 최대 가치
2차원 dp: dp[i][w] = i번째 아이템까지 고려했을 때, 용량 w에서의 최적값

 

1차원으로의 dp 압축은 루프 방향으로 “dp[w - wt_i]가 이번 라운드에서의 갱신 여부”를 통제해, 아이템의 중복을 허용할지 결정한다.

1. 0/1 배낭

• 각 아이템 최대 1개 선택 가능
• 전이
  1차원: dp[w] = max(dp[w], dp[w-wt[i]] + val[i]) ->  w를 뒤에서 앞으로 순회
  2차원: dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt_i] + val_i) -> 전부 이전 층을 확인해서 아이템 i는 최대 한 번 사용

2. 완전 배낭

• 같은 아이템을 여러 번 사용 가능
• 전이
  1차원: dp[w] = max(dp[w], dp[w-wt[i]] + val[i]) -> w를 앞에서 뒤로 순회
  2차원: dp[i][w] = max(dp[i-1][w], dp[i][w - wt_i] + val_i) -> i층을 또 확인 가능

2차원 dp 테이블을 채우는 것도 O(n^2)의 시간 복잡도가 필요하기 때문에 공간 복잡도가 유리한 1차원 dp로 풀이하도록 하자!