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

문제 이해하기

똑같이 풀면 될거같은데?

1차 코드

/*
 * 2025-07-07
 * 문제052 -백준 1516 게임개발하기
 * */
package day8.B1516;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        List<List<Integer>> list = new ArrayList<>();
        int[] time = new int[N];
        int[] array = new int[N];
        int[] rslt = new int[N];

        for(int i = 0; i < N; i++){
            list.add(new ArrayList<>());
        }

        for(int i = 0; i <N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i] = Integer.parseInt(st.nextToken());

            while(Integer.parseInt(st.nextToken()) != -1){
                list.get(i).add(Integer.parseInt(st.nextToken()));
                array[i]++;
            }
        }

        Queue<Integer> queue = new LinkedList<>();

        // 제일 처음 초기화
        for(int i = 0; i < N; i++){
            if(array[i] == 0){
                queue.offer(i);
                rslt[i] = time[i]; // 처음 시작하는 건 거기에 걸리는 시간 = 최종 걸리는 시간

            }
        }
        
        while(!queue.isEmpty()){
            int current = queue.poll();
            for(int next : list.get(current)){
                array[next]--;
                
                
                
                if(array[next] == 0){
                    queue.offer(next);
                }
            }
        }

        br.close();
    }
}

문제는 이제.. 시간을 어떻게 누적해서 구할것이냐가 문제.

첫번째 문제 - 입력 받는 부분

st.next를 두번 받고있고 그리고 방향이 i→pre가 아니라 pre→i여야 함.

for(int i = 0; i <N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i] = Integer.parseInt(st.nextToken());

            while(Integer.parseInt(st.nextToken()) != -1){
                list.get(i).add(Integer.parseInt(st.nextToken()));
                array[i]++;
            } // 이렇게 쓰면 한번에 2개를 건너뛰잖아. 안되지
        }

수정한 코드

while (true) {
    int pre = Integer.parseInt(st.nextToken());
    if (pre == -1) break;

    list.get(pre - 1).add(i); // i를 짓기 위해 pre가 먼저
    array[i]++;
}

두번째 틀린 부분 - 누적 로직을 어떻게 작성할 것이냐…

rslt[next] = Math.max(rslt[next], rslt[current] + time[next]);

// 이게 왜 math.max야?