[백준] 2073 수도배관공사

문제

• 수도관을 설치해 D만큼 떨어진 강에서 물을 끌어오기로 했다.
• 근처 인간 마을에서 P개의 파이프를 매입했고 각각은 길이 L과 용량 C로 나타낼 수 있다
• 파이프들을 일렬로 이어서 수도관을 하나로 만들 수 있고, 
  수도관의 용량은 파이프들의 용량 중 최솟값이 되고 수도관의 길이는 파이프들의 총합니다.
• 수도관을 한 개 만들어 총 길이가 정확히 D와 같도록 할 때, 가능한 최대 수도관 용량 구하기

 

• 1 <= D <= 100,000
  1 <= P <= 350

 

풀이

• 파이프를 하나씩 늘려가면서 이전 파이프들과 더해 최대 D길이까지 새로운 파이프를 만들어 간다. 
• 용량이 큰 파이프부터 시작해 길이가 추가될 때마다 작은 용량의 파이프에 맞춰 최대 용량이 정해진다.

 

import sys
input = sys.stdin.readline

D, P = map(int, input().split())
pipe = [tuple(map(int, input().split())) for _ in range(P)]
pipe.sort(key=lambda x: x[1])

# dp[l] : 길이가 l일 때 최대 용량
dp = dict()

while pipe :
    l, c = pipe.pop()
	
    keys = list(dp.keys())	# 현재까지의 파이프 길이
    for k in keys :
    	# 이미 동일한 길이의 파이프가 있는 경우, 최대 용량 비교
        if k+l in dp :
            if dp[k+l] < c :
                dp[k+l] = c
        # D 길이보다 작은 길이의 파이프인 경우 추가
        elif k+l <= D :
            dp[k+l] = c
	
    # 현재 파이프 l 추가
    if (l in dp and dp[l] < c) or l not in dp:
        dp[l] = c

print(dp[D])

 

References

• 파이썬 DP