[백준] 16169: 수행 시간 - JAVA

26 Dec 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

컴퓨터마다 계급이 있어서 i번 컴퓨터가 동작하기 위해서는 i-1번 컴퓨터들이 먼저 동작을 해야한다.

위상정렬을 이용해 구현했다.

컴퓨터들의 정보를 저장하고, 계급의 오름차순으로 i번과 i+1을 연결시키는 연결리스트로 저장했다.

위상정렬을 위한 배열도 저장하여 이 값이 0인 것부터 큐에 넣어 처리해주었다.

---

메모리: 14148KB

시간: 128ms

언어: Java 11

코드

import java.io.*;
import java.util.*;

public class Main {
    static class Computer {
        int idx;
        int rank;
        int speed;

        public Computer(int idx, int rank, int speed) {
            this.idx = idx;
            this.rank = rank;
            this.speed = speed;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Computer[] computers = new Computer[n];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int rank = Integer.parseInt(st.nextToken());
            int speed = Integer.parseInt(st.nextToken());
            computers[i] = new Computer(i, rank, speed);
        }

        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        int[] inDegree = new int[n];
        for (int i = 0; i < n; i++) {
            int currentRank = computers[i].rank;
            for (int j = 0; j < n; j++) {
                int nextRank = computers[j].rank;
                if (nextRank - 1 == currentRank) {
                    inDegree[j]++;
                    list.get(i).add(j);
                }
            }
        }

        int[] time = new int[n];
        Queue<Computer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.add(computers[i]);
                time[i] = computers[i].speed;
            }
        }

        int answer = 0;
        while (!queue.isEmpty()) {
            Computer currentComputer = queue.poll();

            for (int nextIndex : list.get(currentComputer.idx)) {
                Computer nextComputer = computers[nextIndex];

                int calculatedSpeed = (int) (Math.pow((currentComputer.idx - nextComputer.idx), 2)
                        + currentComputer.speed);
                time[nextIndex] = Math.max(calculatedSpeed + nextComputer.speed, time[nextIndex]);

                answer = Math.max(answer, time[nextIndex]);

                inDegree[nextIndex]--;
                if (inDegree[nextIndex] == 0) {
                    queue.add(new Computer(nextComputer.idx, nextComputer.rank, time[nextIndex]));
                }
            }
        }

        System.out.println(answer);
    }

}