99클럽 코테 스터디 17일차 TIL [DP]

- 오늘의 학습 키워드 : DP

[문제 이름 : 작업 (백준 2056, G4)]
문제 url : https://www.acmicpc.net/problem/2056

내가 작성한 코드는 아래와 같다.

package day_1113;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static ArrayList<Integer>[] list;
    static int[] works;
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int input = Integer.parseInt(br.readLine());
        list = new ArrayList[input+1];
        works = new int[input+1];

        for(int i=1; i<=input; i++) {
            list[i] = new ArrayList<>();
        }

        // 정보 저장
        for(int i=1; i<=input; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int time = Integer.parseInt(st.nextToken());
            int beforeWorks = Integer.parseInt(st.nextToken());
            works[i] = time;
            for(int j=0; j<beforeWorks; j++) {
                int workNum = Integer.parseInt(st.nextToken());
                list[i].add(workNum);
            }
            Collections.sort(list[i]);
        }

        for(int i=1; i<=input; i++) {
            int maxTime = 0;
            for(int time : list[i]) {
                maxTime = Math.max(works[time], maxTime);
            }
            works[i] = maxTime + works[i];
        }

        Arrays.sort(works);
        System.out.println(works[works.length-1]);
    }
}

풀이 과정 (풀이 시간 : 20분)

이게 왜 골드 4 문제지? 하는 느낌이 들었다. 빠르게 문제를 푸는 능력을 기를 수 있었던 것 같아 좋았다.

1. 작업에 걸리는 시간을 works 배열에 저장하고, 선행 작업에 대한 관계를 ArrayList<Integer>[] list에 저장한다. 이때, 선행 작업의 번호를 모두 저장했을 때는, 작은 작업부터 정보를 확인할 수 있도록 list[i]의 ArrayList들을 오름차순으로 정렬한다.

2. 선행 작업들 중, 제일 오래 걸리는 시간을 해당 번호의 작업시간과 더해줘야 한다. 그래서, maxTime으로 선행 작업들 중 제일 오래 걸리는 시간을 저장했고, works[i]마다 해당 작업에 걸리는 시간을 더해주어 이를 갱신했다.

3. 제일 오래 걸리는 시간을 출력하기 위해, works 배열을 정렬한 뒤, 제일 큰 값인 마지막값을 출력해주었다.

내일은 자기 소개서 합격을 위해 문장 정리 및 피드백을 받아보고자 한다.