[ BOJ ][JAVA][1949] 우수마을

www.acmicpc.net/problem/1949

1949번: 우수 마을

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	3531	1556	1055	47.416%

문제

N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있을 때, 두 마을이 인접해 있다고 한다.

이 나라의 주민들에게 성취감을 높여 주기 위해, 다음 세 가지 조건을 만족하면서 N개의 마을 중 몇 개의 마을을 '우수 마을'로 선정하려고 한다.

1. '우수 마을'로 선정된 마을 주민 수의 총 합을 최대로 해야 한다.
2. 마을 사이의 충돌을 방지하기 위해서, 만일 두 마을이 인접해 있으면 두 마을을 모두 '우수 마을'로 선정할 수는 없다. 즉 '우수 마을'끼리는 서로 인접해 있을 수 없다.
3. 선정되지 못한 마을에 경각심을 불러일으키기 위해서, '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다.

각 마을 주민 수와 마을 사이의 길에 대한 정보가 주어졌을 때, 주어진 조건을 만족하도록 '우수 마을'을 선정하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 이하이다. 셋째 줄부터 N-1개 줄에 걸쳐서 인접한 두 마을의 번호가 빈칸을 사이에 두고 주어진다.

출력

첫째 줄에 '우수 마을'의 주민 수의 총 합을 출력한다.

예제 입력 1

7
1000 3000 4000 1000 2000 2000 7000
1 2
2 3
4 3
4 5
6 2
6 7

예제 출력 1

14000

접근

TREE + DP로 DFS로 풀면 시간초과가 나기 때문에 메모이제이션을 이용해야 한다.

조건 3 은 의미 없는 조건임을 파악 하는 것이 핵심이다.

인접한 마을 중 우수 마을이 하나도 없을 경우 그 마을은 2번 조건을 위배하지 않고 우수 마을로 선정할 수 있고, 또한 선정하는것이 항상 이득이다.

따라서 2번 조건만을 고려하면서 최대 합을 구해도 무방하다.

코드

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

public class p1949 {
    static int n;
    static int[] arr;
    static List<Integer>[] list;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1];
        dp = new int[n + 1][2];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        list = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            list[u].add(v);
            list[v].add(u);
        }

        // 트리는 사이클을 이루지 않기 때문에 어느 마을을 root로 선정해도 된다.
        // 편리하게 시작점인 1을 루트로 지정.
        dfs(1, -1);
        bw.write(Math.max(dp[1][0], dp[1][1]) + "\n");
        bw.flush();
    }

    // dp[i][1] : i마을을 우수마을로 선정했을 때의 주민수 총합
    // dp[i][0] : i마을을 우수마을로 선정하지 않았을 때의 주민수 총합

    static void dfs(int now, int parent) {
        for (int adj : list[now]) {
            if (adj != parent) {
                // 루트에서 리프노드까지 top-down으로 내려간 후
                dfs(adj, now);
                // 다시 리프노드에서부터 위로 올라가면서 dp 배열을 업데이트
                dp[now][1] += dp[adj][0];
                dp[now][0] += Math.max(dp[adj][0], dp[adj][1]);
            }
        }
        dp[now][1] += arr[now];
    }
}