[DP] 호텔(Python)

문제링크

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

1106번: 호텔

1. 핵심

• 유형2-1. item을 중복해서 사용 가능 + 유형3. weight를 특정할 수 없는 경우
• 최소 비용을 고르기 때문에 보통은 도시(item) / 고객수(weight) / 비용(value)로 고객수 i명을 확보하기 위한 비용j라고 dp[i][j]를 정의할 수 있다.
• 하지만 문제는, 고객의 수, 즉 weight가 '무한'이므로 고객수를 특정할 수 없다는 것이다. 따라서 유형3으로 weight와 value를 변경해서 도시(item) / 고객수(value) / 비용(weight)로 생각해 dp[i][j]는 비용i에 대한 확보한 고객수 j라고 보는 것이 합리적이다.
• 그렇다면, 같은 관점으로 비용도 특정할 수 있는가에 대한 판단을 해야한다. 
  • 비용은 최대 100 든다. 그러므로 최대 비용은 특정 도시에서 1명을 확보하는데 100이 든다고 가정했을 때, 최대 1000명까지 확보해야할 수 있으므로 최대비용은 100 * 1000으로 확정할 수 있다.
• 코드해설
  • dp의 열을 나타내는 것이 weight, 즉 비용이므로 max_cost를 활용해서 1차원 dp 테이블을 생성한다.
    • 유형2-2. 중복사용 불가의 경우 dp 테이블은 1차원이 필요하지만 중복사용의 경우 1차원 테이블로도 충분히 풀 수 있다.
  • 초기값을 설정한다. 비용이 0원, 즉 홍보를 하지 않았을 때 확보되는 고객수는 존재하지 않으므로 0이다. dp[0] = 0
  • dp[i]는 i 비용을 썼을 때 확보되는 고객 수이다. 중복사용 가능하므로 앞에서부터 볼 수 있다. range(1, max_cost + 1)
  • i번 비용을 만들기 위해서 dp[i - w]  + v 가 최대가 되는 값을 찾는다.
    • dp[i - w] + v .. 1 <= w <= i .. 
  • 고객 c명을 확보하기 위한 최소 비용을 구해야하는데 weight가 비용이고 이는 곧 idx를 의미한다. for문 돌면서 c를 넘는 비용 중 최소 비용을 갱신해서 찾아낸다.

2. 코드(Python)

c, n = map(int, input().split())
# (비용, 고객 수)
infos = [list(map(int, input().split())) for _ in range(n)]

def sol_1():
    # 동전을 배수로 쓸 수 있다 > 동전을 중복해서 사용할 수 있다!!
    # 앞에서부터 보면 된다.
    # 특정 도시(item) - 고객(weight) / 비용(value)
    # 문제는 '고객'을 특정할 수 없는 상황 > 따라서 고객과 비용을 반대로 생각해야함.
    # 특정 도시(item) - 고객(value) / 비용(weight)
    # 최대비용 1000명 홍보
    # 비용100 1명
    # 비용 100 * 1000 => 1000명 홍보 가능!!
    max_cost = 100 * 1000
    # 비용i원일 때 얻는 최대 고객의 수!
    # 중복사용가능 > 1차원 > dp[i] weight를 i얻을 때 최대, 최소 value
    dp = [-1 for _ in range(max_cost + 1)]
    
    dp[0] = 0
    for w, v in infos:
        for i in range(1, max_cost + 1):
            if w <= i:
                dp[i] = max(dp[i], dp[i - w] + v)

    # idx가 곧 비용을 의미함
    min_cost = max_cost
    for idx, cus_num in enumerate(dp):
        if c <= cus_num:
            min_cost = min(min_cost, idx)
                        
    return min_cost

print(sol_1())