수도배관공사

[BOJ/백준] 02073 - 수도배관공사

DP[N] = 길이 N을 만들기위한 최대용량 제목 수도배관공사 조건 시간 제한 : 2 초 메모리 제한 : 128 MB 문제 아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7 ≤ D ≤ 100,000)만큼 떨어진 곳의 강에서 물을 끌어오기로 했다. 근처의 인간 마을에서 P개(1 ≤ P ≤ 350)의 파이프를 매입했는데, 각각은 길이 Li와 용량 Ci로 나타낼 수 있다. (Li와 Ci는 모두 2^23보다 작거나 같은 양의 정수이다) 파이프들은 일렬로 이어서 수도관 하나로 만들 수 있으며, 이때 수도관의 용량은 그것을 이루는 파이프들의 용량 중 최솟값이 되고, 수도관의 길이는 파이프들 길이의 총합이다. 수도관을 한 개 만들어 ..