person3113

늙어서 은퇴하기 전까진 계속 공부하자!!


느낀점

  • 코드 중 다음 한 가지를 이해하는 데 애를 먹다가 대략은 이해해서 기록해 본다. answer[next] = Math.max(answer[next], answer[now] + time[now]);
  • 아마 내가 문제를 잘 이해하지 못해서 위 코드를 파악하는 데 애를 먹은 것 같다. 아래 예시를 가지고 이해 해보자.
    • 조건에서 여러 개의 건물을 동시에 지을 수 있다고 나온다. 즉 1000 1 2 3 -1 부분을 이해하면, 4번을 지으려면 1,2,3번을 먼저 지어야 한다. 이 때 1,2번은 동시에 지을 수 있다. 그리고 3번은 먼저 1,2번을 지어야지 지을 수 있다. 따라서 1,2번을 동시에 지을 때 2번은 10초만에 지을 수 있지만 1번은 20초 걸려야 된다(+20초). 그 후 3번을 짓기 시작한다(+1초). 그 후 4번을 지으면 총 20+1+1000초의 시간이 걸린다. 
      4
20 -1         // 출력: 20
10 -1         // 출력: 10
1 1 2 -1      // 출력: 21
1000 1 2 3 -1 // 출력: 1021
    • 아래 풀이 코드 중 while (!queue.isEmpty())부분 안에서 answer[next] = Math.max(answer[next], answer[now] + time[now]);를 중심으로 보자.
      • answer[4]이 업데이트되는 식을 보면, answer[4] = Math.max(answer[4], answer[1] + time[1]);에서 answer[4] = max(0, 0+20)는 20이 된다.
      • 그 후 answer[4] = Math.max(answer[4], answer[2] + time[2]);에서 answer[4] = max(20, 0+10)는 20이 된다.
      • 그 후 answer[4] = Math.max(answer[4], answer[3] + time[3]);에서 answer[4] = max(20, 20 + 1);는 21이 된다.
      • 마지막에 answer[i] += time[i]; 자기 자신을 짓는 시간을 추가하므로 최종적으로 4번은 1021초가 걸린다.
  • 즉 위 과정을 보면 max의 역할을 짐작할 수 있다. 1000 1 2 3 -1에서 4번을 지으려면 1,2번->3번->4번 순으로 지어야 한다. 조건에서 여러 개의 건물을 동시에 지을 수 있으므로, 1,2번을 동시에 짓는다. 이 때 2번이 10초만에 지을 수 있지만, 1번은 20초가 필요해서 아직 건설 중이다. 따라서 3번을 지을 수 없는 상황이라 20초까지 기다린 후 넘어간다. 이 때 max가 필요한 것이다.
  • answer[4] = Math.max(answer[4], answer[1] + time[1]);에서 answer[4] = max(0, 0+20)는 20이 된다. 그 후 answer[4] = Math.max(answer[4], answer[2] + time[2]);에서 answer[4] = max(20, 0+10)이 실행된다. 따라서 이런 경우를 위해서 max가 있는 것이다.



문제

게임 개발 (백준: 1516번)

image



풀이

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        ArrayList<Integer>[] list = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        int[] indegree = new int[n + 1];
        int[] time = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            time[i] = sc.nextInt();
            int nextInput;
            while ((nextInput = sc.nextInt()) != -1) {
                list[nextInput].add(i);
                indegree[i]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

        int[] answer = new int[n + 1];
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int next : list[now]) {
                indegree[next]--;
                answer[next] = Math.max(answer[next], answer[now] + time[now]);
                if (indegree[next] == 0) {
                    queue.add(next);
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            answer[i] += time[i];
            System.out.println(answer[i]);

        }
    }

}

참고