[Java] 백준 2056번 : 작업

문제소개

 

해결과정

DP를 활용해 풀이했다.

1. 각 노드를 인접리스트 방식을 이용해 그래프로 표현한다.

2. 1차원 dp 배열을 생성한다.

3. 각 노드별 소모되는 시간을 담는 1차원 배열을 생성한다.

4. 1번노드부터 순차적으로 점화식을 이용한 Bottom-up 방식의 DP를 적용한다.

5. 점화식은 다음과 같이 표현될 수 있다.

for (int i = 1; i < N + 1; i++) {
	dp[i] = graph[i].stream()
		.mapToInt(n -> dp[n])
		.max()
		.orElse(0) + costArr[i];
}

 

6. 현재 노드를 방문할 때, 나에게 연결되어 있는 노드들이 전부 노드 번호가 작다는 조건이 명시되어있으므로 가능한 풀이이다.

7. 현재 노드 기준, 나에게 연결되어 있는 노드들까지 걸린 소요시간 중 최대 시간을 선택하고, 현재 노드의 소모되는 시간을 더해준다.

문제의 조건 중 나에게 연결되어 있는 노드들이 전부 수행된 이후에야 현재 노드의 작업을 진행할 수 있기 때문에 최대 시간을 선택해줘야한다.

 

솔루션

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

public class Main {

    static int N;
    static ArrayList<Integer>[] graph;
    static int[] costArr;
    static int[] dp;

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

        N = Integer.parseInt(br.readLine());
        graph = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            graph[i] = new ArrayList<>();
        }
        costArr = new int[N + 1];
        dp = new int[N + 1];

        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int num = Integer.parseInt(st.nextToken());
            costArr[i] = cost;
            if (num != 0) {
                for (int j = 0; j < num; j++) {
                    int node = Integer.parseInt(st.nextToken());
                    graph[i].add(node);
                }
            }
        }

        for (int i = 1; i < N + 1; i++) {
            dp[i] = graph[i].stream()
                    .mapToInt(n -> dp[n])
                    .max()
                    .orElse(0) + costArr[i];
        }

        int result = Arrays.stream(dp)
                .max()
                .orElse(-1);

        System.out.println(result);

    }
}