Python - [백준]2073-수도배관공사

출처

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

문제

배관을 사용하여 수도관을 만드는데, 그 중 최대용량이 되도록 만드는 문제이다.

접근방법

처음에 문제 이해 자체를 잘못하여 많이 돌아온 문제이다. 문제를 정확히 이해해보면, 파이프를 이용하여 딱 길이가 D인 수도관을 만들 것인데, 수도관의 용량은 그것을 구성하는 파이프들의 용량 중 최솟값이다. 다시말해 여러 조합들로 만들 수 있지만 용량은 그것중 가장 작은 값이 된다는 말이다.
그 중 최대용량이 되도록 파이프를 조합해보는 문제이다.DP문제인 만큼, 현재 상태를 기록해가며 문제를 풀 수 있도록 점화식을 만들어 보았다.

풀이

여러 파이프를 한번에 받기 보다는, 그때 그때 입력받아서 이 파이프를 사용할 것인지 아닌지를 판별하는 방식이 메모리와 시간을 맞출 수 있는 방법이다.

길이가 L이고 용량이 C인 파이프가 입력으로 주어진다. 그렇다면 이 파이프를 사용하는 경우와 사용하지 않는 경우중 최대의 용량을 선택하면 된다.

• 주어진 파이프를 사용하는 경우 : 길이 dp[i]의 파이프는 dp[i-l]과 현재 파이프의 용량 중 최솟값을 선택하면 된다.
  (ex. 길이가 4인 파이프가 들어온 경우, 6의 길이를 가지는 파이프는 (기존에 저장해둔 길이 2의 용량의 최댓값, 현재 길이4인 파이프의 용량) 둘 중 최소값의 용량을 가질것이다. ) 4와 2인 파이프를 이으면 6이 되기때문이다.
• 주어진 파이프를 사용하지 않은 경우 : 기존에 저장된 dp값이다
• 최종적으로 점화식은 dp[i]=max(dp[i], min(dp_copy[i-l],c))가 된다.

개인적으로 매우 어렵고 이해하는데도 오래걸린 문제였다.

import sys
input = sys.stdin.readline
D, P = map(int, input().split())
dp = [0] * (D + 1)
dp[0] = 1e9 ##무한대의 값을 나타내기 위함
for _ in range(P):
    l, c = map(int, input().split())
    tmp = dp[:]
    for i in range(l, D + 1):
        if tmp[i-l]:
            dp[i] = max(dp[i], min(tmp[i - l],c)) # 사용할 경우, 사용하지 않을 경우 중 최대값을 저장
        
print(dp[D])