[백준 2073번] 수도배관공사 (python)

문제

아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7<=D<=100,000)만큼 떨어진 곳의 강에서 물을 끌어오기로 했다. 근처의 인간 마을에서 P개(1<=P<=350)의 파이프를 매입했는데, 각각은 길이 Li와 용량 Ci로 나타낼 수 있다. (Li와 Ci는 모두 24비트 양의 정수이다)

파이프들은 일렬로 이어서 수도관 하나로 만들 수 있으며, 이때 수도관의 용량은 그것을 이루는 파이프들의 용량 중 최솟값이 되고, 수도관의 길이는 파이프들 길이의 총합이다.

수도관을 한 개 만들어 총 길이가 정확히 D와 같게 할 때, 가능한 최대 수도관 용량을 구하는 프로그램을 작성하시오.

 

기록

(dp 13일차) 오늘따라 시간 초과 메모리초과가 많이 나서 pypy3로 제출했다. 이차원 배열로 했을 때 메모리초과가 떠서 1차원 배열 두 개 생성해서 하나는 계속해서 파이프 최대용량을 갱신하는 용도, 하나는 각 파이프 적용때마다 일시적으로 사용하는 용도로 사용했다. 

 

이번 문제는 기존 dp문제와 비슷했지만 파이프 중 최소 파이프가 값이 된다는 점에서 조금 달랐던 것 같다. 평범한 dp점화식에 한번 더 min으로 작은 파이프 적용시켰다. dp[i]에는 i길이의 파이프의 최대용량을 저장하며, dp[i] = max(i길이의 파이프용량, min(현재파이프 l을 추가하기 전 i-l길이의 파이프용량, 현재파이프 l의 용량)) 이렇게 점화식 세워서 풀었다.

 

코드

import sys
input = sys.stdin.readline

d, p = map(int, input().split())
dp = [1e9]+[0]*d
for _ in range(p):
    l, c = map(int, input().split())
    dp_max = dp.copy()
    for i in range(l, d+1):
        if dp_max[i-l] :
            dp[i] = max(dp[i], min(dp_max[i-l], c))
print(dp[d])

1. 길이마다 파이프 최대용량 저장할 일차원 배열 dp생성

2. 파이프 순서대로 돌면서 dp[i] = max(i길이의 파이프용량, min(현재파이프 l을 추가하기 전 i-l길이의 파이프용량, 현재파이프 l의 용량)) 수행하며 배열의 파이프 최대용량 갱신

3. d 길이의 파이프 최대용량 출력