글 읽기 - 적절한 반례가 안보이네요..

giyeon95 3년 전 0

위상정렬을 이용했고,

Queue 두개를 이용해서 동시진행 작업의 경우 max 값을 구해서 정답에 더해주는 방식입니다.

혹시 반례 보이시는게 있는지 해서 질문드려요.

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

public class Main {

    static int n;

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

        n = sc.nextInt();

        List<List<Integer>> nodes = new ArrayList<>();
        int[] inEdgeCnt = new int[n];
        int[] nodeCosts = new int[n];

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

        for (int i = 0; i < n; i++) {
            int cost = sc.nextInt();
            int precedeCnt = sc.nextInt();

            nodeCosts[i] = cost;

            for (int j = 0; j < precedeCnt; j++) {
                int preNode = sc.nextInt() - 1;

                nodes.get(preNode).add(i);

                ++inEdgeCnt[i];
            }
        }

        System.out.println(getMinCost(nodes, inEdgeCnt, nodeCosts));
    }

    static int getMinCost(List<List<Integer>> nodes, int[] inEdgeCnt, int[] nodeCosts) {
        boolean[] check = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        Queue<Integer> nextQ = new LinkedList<>();

        int anw = 0;

        for (int i = 0; i < inEdgeCnt.length; i++) {
            if (inEdgeCnt[i] == 0) {
                q.add(i);
            }
        }

        int nodeCost = Integer.MIN_VALUE;

        while (!q.isEmpty()) {
            int p = q.remove();
            check[p] = true;

            nodeCost = Math.max(nodeCost, nodeCosts[p]);

            nodes.get(p).forEach(v -> {
                if (--inEdgeCnt[v] == 0) {
                    nextQ.add(v);
                }
            });

            if (q.isEmpty()) {
                q.addAll(nextQ);
                nextQ.clear();

                anw += nodeCost;
                nodeCost = Integer.MIN_VALUE;
            }
        }

        return anw;
    }
}

pl0892029 3년 전 3

작업 A가 진행되어야 작업 B, C가 진행될 수 있고, 작업 B가 진행되어야 작업 D가 진행될 수 있다고 가정해봅시다.

이 때 작업 D가 진행할 수 있는 시간은 작업 B에 종속되어있으므로, 작업 C에 영향을 받으면 안됩니다.

giyeon95 3년 전 3

pl0892029 님 감사합니다.

제가 종속되어있어야 한다고 문제를 잘못 이해 했네요..

4
10 0
6 1 1
7 1 1
5 1 2

위 코드 값: 22

정답이 되어야하는 값: 21

0hye 3년 전 0

pl0892029, giyeon95님 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

적절한 반례가 안보이네요..

giyeon95 3년 전 0

pl0892029 3년 전 3

giyeon95 3년 전 3

0hye 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말