[BOJ] 2073 수도배관공사 (node.js)

BOJ 문제 2073번의 풀이 과정을 작성한 게시글입니다.

 

링크

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

 

문제

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

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

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

 

풀이 과정

접근 방법 1 : 2차원 DP

전체 파이프를 조합해서 최대 수도관의 용량을 구하는 문제이고, 파이프의 길이가 D라고 할 때 각 파이프를 넣을지 안넣을지에 따라 부분적인 구조로 나눌 수 있기 때문에 냅색 알고리즘을 사용하고자 했다.

 

2차원 DP 테이블을 i가 고려하는 파이프의 번호, j가 전체 수도관의 길이라고 할 때,

dp[i][j]에 저장하는 값을 파이프 i번까지 고려했을 때, 수도관 길이가 j일 때의 최대 수도관 용량으로 정의하면

 

수도관의 거리 : 7, 파이프의 갯수가 : 6이고

각 파이프 정보는 첫 번째 열에 기재된 정보와 같다고 할때 다음과 같이 2차원 DP 테이블을 채울 수 있다.

	1	2	3	4	5	6	7
1번 [길이 4, 용량 5]	0	0	0	5	0	0	0
2번 [길이 3, 용량 6]	0	0	6	0	0	0	5
3번 [길이 2, 용량 7]	0	7	0	0	6	0	0
4번 [길이 1, 용량 4]	4	0	4	0	0	4	0
5번 [길이 6, 용량 7]	0	0	0	0	0	7	4
6번 [길이 1, 용량 5]	5	0	0	0	0	0	5

 

하지만 2차원 배열으로 문제를 풀게 되면 메모리 제한을 초과하게 된다.

그 이유는 행인 파이프 갯수 P의 최대가 350이고, 열인 수도관의 길이가 최대 100,000이기 때문이다. (35,000,000 x 8 = 약 280MB)

따라서 2차원 DP를 사용하지 않고 1차원 DP를 사용해서 풀어야 한다.

 

접근 방법2 : 1차원 DP

각 DP 배열에는 수도관 길이가 i일 때 가능한 최대 수도관 용량을 저장한다.

2차원 DP로 저장된 값을 1차원으로 저장할 수 있는 이유는 현재 파이프 상태(dp[i])를 계산할 때는 이 전단계의 파이프(dp[i-현재 파이프의 길이])의 최적값만 필요하기 때문이다.

 

또한 DP 배열을 갱신할 때는 길이가 D일 때부터 거꾸로 접근해야 하는데, 그 이유는 만약 길이가 0일 때 부터 순차적으로 접근하면 파이프를 중복으로 사용하는 경우가 생기기 때문이다.

 

예를 들어 길이 3, 용량 5인 파이프 A에 대해서 수도관 길이가 0일 때 부터 7일 때 까지 반복문을 순회한다고 가정하면

dp[3]의 최대 수도관 용량이 5라고 결정되었고 (파이프 A를 사용하는 경우)

dp[6]의 최대 수도관 용량을 구할 때, dp[3]의 값을 재사용하게 되어 dp[6]을 5라고 결정하게 된다면, dp[6]에 저장된 값은 파이프 A를 2번 사용한 결과가 되는 셈이다.

 

즉, DP 배열의 최적해를 갱신한 다음에, 해당 DP값을 재사용하지 못하게 하기 위해서 길이가 D일때 부터 0일 때까지 감소하면서 dp값을 갱신해야 한다. 이는 파이프를 중복해서 사용할 수 없기 때문이다.

 

1차원 DP를 통해 갱신된 결과는 아래와 같다.

	1	2	3	4	5	6	7
수도관의 길이가 i일 때 수도관의 최대 용량	5	7	6	5	6	7	5

 

 

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const [D, P] = input[0].split(" ").map(Number);
const pipe = input.slice(1).map((x) => x.split(" ").map(Number));

const dp = Array.from({ length: D + 1 }, () => 0);
dp[0] = Infinity;

for (let i = 0; i < P; i++) {
  const [l, c] = pipe[i];

  for (let j = D; j >= l; j--) {
    if (j - l >= 0) {
      dp[j] = Math.max(dp[j], Math.min(dp[j - l], c));
    }
  }
}

console.log(dp[D]);

 

후기

일반적인 냅색 알고리즘을 응용하는 문제인 듯 하다.

1차원 배열의 값을 어떤 순서로 갱신해야 할지 감이 안잡혔던 문제였다. 그리고 파이프를 중복 사용하지 않기 위해 인덱스를 뒤집어서 접근해야 하는 것에 주의해야 한다.

 

참고

https://boomrabbit.tistory.com/123

[ boj : 2073 ] 수도배관공사