[BOJ] 2056 작업 (node.js)

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

 

링크

 

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

 

문제

수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다.

몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들 중에는, 그것에 대해 선행 관계에 있는 작업이 하나도 없는 작업이 반드시 하나 이상 존재한다. (1번 작업이 항상 그러하다)

모든 작업을 완료하기 위해 필요한 최소 시간을 구하여라. 물론, 서로 선행 관계가 없는 작업들은 동시에 수행 가능하다.

 

풀이 과정

접근법 : dp

구해야 하는 것은 모든 작업을 완료하기 위해 필요한 최소 시간이다.

그렇다면 작업을 최소 시간으로 완료하기 위해서 고려해야 하는 점은 뭘까?

 

그것은 바로 선수 작업이 모두 완료된 작업이라면, 해당 작업을 즉시 수행해야 한다는 것이다.

예를 들어 4번 작업의 선행 작업이 1번과 2번이고, 1번은 5시에, 2번은 7시에 끝났다면 4번은 7시에 작업을 바로 시작해야 한다는 점이다.

(선행 관계가 없는 작업들은 동시에 수행이 가능하므로 선행 작업이 끝났다면 다른 작업과 상관없이 현재 작업을 바로 이어서 할 수 있다.)

 

또한 주목해야 할 점은 K번 작업을 시작하기 전에 완료되어야 하는 작업들은 모두 1이상 K-1 이하의 작업이다. (ex) 3번 작업의 선행 작업은 1~2 사이의 작업이 된다.)

즉, K번 작업이 걸리는 최소 시간을 1~K-1까지 결정된 최적화로 구할 수 있다는 것이다.

 

예를 들어

번호	걸리는 시간	선행 작업
1	4	0
2	2	1
3	4	1
4	7	2, 3

 

위의 예시가 있을 때 아래 표를 채워보자.

작업 번호	1번	2번	3번	4번
걸리는 최소 시간	0	0	0	0

 

 

1) 1번

1번은 선행 작업이 없으므로 0~4시간을 소요한다.

작업 번호	1번	2번	3번	4번
걸리는 최소 시간	4	0	0	0

 

2) 2번

2번의 선행 작업은 1번이다. 1번은 4시에 끝나므로 1번이 끝난 바로 직후인 4~6 동안 작업을 수행해야 한다.

작업 번호	1번	2번	3번	4번
걸리는 최소 시간	4	6	0	0

 

3) 3번

3번의 선행 작업은 1번이다. 1번은 4시에 끝나므로 1번이 끝난 바로 직후인 4~8 동안 작업을 수행해야 한다.

작업 번호	1번	2번	3번	4번
걸리는 최소 시간	4	6	8	0

 

4) 4번

4번의 선행 작업은 2, 3번이다.

2번은 6시에 끝나고, 3번은 8시에 끝난다.

그렇다면 4번은 2번과 3번이 모두 끝나야 작업을 시작할 수 있기 때문에 더 늦게 끝나는 3번이 끝난 이후부터 작업을 시작할 수 있다.

즉, 8~15시까지 작업을 수행한다.

작업 번호	1번	2번	3번	4번
걸리는 최소 시간	4	6	8	15

 

결과적으로 최소로 걸리는 작업 시간은 15시가 된다.

또한 주의할 점은 항상 dp 배열의 마지막 원소를 출력하는 것이 아닌 전체 dp 배열 중에서 최댓값을 출력해야 한다는 점이다.

그 이유는 작업 번호가 더 작더라도 더 늦게 끝나는 작업이 있을 수 있기 때문이다.

 

코드

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

const N = +input[0];
const info = input.slice(1).map((x) => x.split(" ").map(Number));

const dp = Array.from({ length: N + 1 }, () => 0); // 모든 작업을 완료하기 위한 최소 시간
dp[1] = info[0][0];

for (let i = 2; i <= N; i++) {
  const [time, cnt, ...nums] = info[i - 1];

  dp[i] = time;

  for (let num of nums) {
    dp[i] = Math.max(dp[i], dp[num] + time);
  }
}

console.log(Math.max(...dp));

 

후기

무난한 dp 문제였다.

위상 정렬의 풀이도 존재하는 듯 했다.