BOJ) 작업 (2056 번)

작업

2056번: 작업

작업의 개수 N이 주어지고, 다음 N줄에 거쳐 각 작업의 수행 시간과 선행돼야하는 작업의 숫자가 주어진다.

K작업에서 선행되는 작업은 1 ~ K-1 사이의 작업이 주어진다.

이 문제는 DP와 위상정렬로 분류되어있다.

그래서, 위상정렬로 접근하려고 했다.

ArrayList에 각 선행되는 작업들을 넣어주고, 선행작업이 없는 작업들을 Queue에 넣어주어 순회했었다.

각 작업은 상관관계가 없으면 동시에 진행되니까, group을 넣어주고, depth를 함께 저장하면서 시간이 겹치지 않게 구하려고 했었다.

 

하지만, 로직과 코드가 복잡해지고 올바르지 않다는 생각이 들었다.

문제를 다시 봤는데, 친절하게도 힌트에 각 작업의 수행 시간이 적혀있었다.

여기서 든 생각이, 각 작업의 시작 시간을 저장해주면 쉽게 구할 수 있지 않을까? 였다.

그래서 입력부터, 각 작업의 ( 선행 작업의 수행 시간 + 선행 작업의 대기 시간 ) 의 최댓값을 저장해주었다.

(그래야, 병렬로 진행되는 작업들을 선별해내 최소 시간에 진행할 수 있기 때문)

 

이렇게 저장하고 보니까 어렵게 접근할 필요도, 풀어갈 필요도 없었다.

문제를 쉽게 접근하는 시야를 기르자.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Work_2056 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int[] times = new int[n+1]; // 작업에 걸리는 시간
    int[] startingTime = new int[n+1]; // 선행 작업 이후 언제 시작하는지 저장

    for(int i=1; i<=n; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      times[i] = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      while(m-- >0) {
        int parent = Integer.parseInt(st.nextToken());
        startingTime[i] = Math.max(startingTime[i], startingTime[parent] + times[parent]);
      }
    }

    br.close();
    solution(n, times, startingTime);
  }

  private static void solution(int n, int[] times, int[] startingTime) {
    int answer =0;
    for(int i=1; i<=n; i++) {
      answer = Math.max(answer, startingTime[i]+times[i]);
    }
    System.out.println(answer);
  }
}