최솟값들로 배낭을 구성하고 이들 중 최댓값을 찾아야하는 특이한 배낭문제

2073번: 수도배관공사

 

길이가 L, 용량이 C인 파이프들이 주어질때, 이들을 적절히 선택하여 길이가 정확히 D가 되도록 한다

 

이때 수도관의 용량은 선택한 파이프들의 용량들 중 최솟값이 된다

 

그리고 길이는 선택한 파이프들의 길이의 총합이다.

 

이때, 가능한 수도관 용량들 중 최댓값을 구한다

 

------------------------------------------------------------------------------------------------------------------------------------

 

단순한 배낭 문제라고 생각해서

 

from sys import stdin

d,p = map(int,stdin.readline().split())

A = []

for _ in range(p):
    
    l,c = map(int,stdin.readline().split())
    A.append((l,c))

INF = 10**18
dp = [INF]*(d+1)

for l,c in A:
    
    for i in range(d,l-1,-1):
        
        dp[i] = min(dp[i-l], c)

print(dp[d])

 

 

이런식으로 dp[i] = 길이가 i일때 수도관 용량의 최솟값이라 설정하면

 

dp[i] = min(dp[i-l], c)일테니까

 

근데 생각해본게 문제는 길이가 d인 수도관 용량들 중 최댓값을 구하라는게 문제더라고

 

근데 배낭에 담을 때는 수도관들의 용량중 최솟값이 dp[i]가 된다는거

 

배낭에 담을 때 길이가 d가 되는 경우는 여러가지가 있을 수 있으니까 그들 중 최댓값을 찾으라는건가?

 

1 3

2 1

3 2

2 4

4 5

 

이렇게 있는데 길이가 4인 경우는 [(1,3), (3,2)], [(2,1), (2,4)], [(4,5)] 여러가지 있잖아

 

이들은 각각 용량이 2, 1, 5일테고 이 중 최댓값은 5니까

 

INF = 10**18
dp = [INF]*(d+1)

answer = 0

for l,c in A:
    
    for i in range(d,l-1,-1):
        
        dp[i] = min(dp[i], dp[i-l], c)

        if dp[d] != INF:
            
            if answer < dp[d]:
                
                answer = dp[d]

print(answer)

 

 

그래서 뭐 이런식으로 dp[d]가 INF가 아니라면 dp[d]가 계산된거니까 여기서 최댓값 answer을 갱신하는 식으로

 

근데 틀리더라

 

그래도 생각해보면 

 

dp[i] = "길이가 i인 수도관에서 수도관들의 용량들 중 최솟값의 최댓값" 

 

(l,c)를 받아오면 이전까지 계산한 값은 dp[i-l]에 있는데 여기서 l,c를 담으면 min(dp[i-l],c)인데

 

v = min(dp[i-l],c)라 하면 이들 중의 최댓값을 찾아야하니까

 

dp[i] = max(dp[i], v) = max(dp[i], min(dp[i-l], c))

 

i = d인 경우 dp[d]가 찾고자하는 정답이 되는

 

또 중요한 점은 많이 쓰인 부분이지만 dp[i-l] != -1인 경우에 계산을 해야한다는거

 

dp[i-l] = -1인 경우는 길이가 i-l인 수도관이 불가능하다는 뜻이거든

 

from sys import stdin

d,p = map(int,stdin.readline().split())

INF = 10**18
dp = [-1]*(d+1)
dp[0] = INF

A = []

for _ in range(p):
    
    l,c = map(int,stdin.readline().split())
    A.append((l,c))
    
for l,c in A:
    
    for i in range(d,l-1,-1):
        
        if dp[i-l] != -1:

            dp[i] = max(dp[i], min(dp[i-l], c))

print(dp[d])

 

 

여기서 중요한 부분은 dp = [-1]*(n+1)로 하고 dp[0] = INF로 설정해야

 

dp = [INF]*(n+1)로 하면 dp[i] = INF로 되어있어서 max(dp[i], min(dp[i-l],c))는 INF로 나올걸