핵심
- 3번 조건으로 많이 헤맸다.
- 문제의 1번 조건에 의해 3번 조건은 불만족 시 모순이 된다
- A - B - C 로 연결되어 있다고 해보자
- A와 C가 모두 우수로 선정되지 않았을 때
- B도 우수로 뽑히지 않은 것이 최대라고 가정해보면
- B를 우수로 뽑았을 때 더 값이 커지므로 모순이 됨을 확인할 수 있다.
- 따라서 3번 조건을 고려할 필요가 없음.
코드
package Baekjoon;
import java.io.*;
import java.util.*;
public class Algo1949 {
static int N;
static int[] population;
static ArrayList<Integer>[] map;
static int[][] memo;
static int result = 0;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
population = new int[N+1];
map = new ArrayList[N+1];
memo = new int[2][N+1];
for(int i=0; i<=N; i++) map[i] = new ArrayList<>();
st = new StringTokenizer(br.readLine());
for(int i=1; i<=N; i++) {
population[i] = Integer.parseInt(st.nextToken());
}
for(int i=1; i<=N; i++) {
memo[1][i] = population[i];
}
for(int i=0; i<N-1; i++) {
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
map[v1].add(v2);
map[v2].add(v1);
}
dfs(1, 0);
System.out.println(Math.max(memo[0][1], memo[1][1]));
}
private static void dfs(int current, int parent) {
for(int next : map[current]) {
if(next==parent) continue;
dfs(next, current);
memo[1][current] += memo[0][next];
memo[0][current] += Math.max(memo[0][next], memo[1][next]);
}
}
}
- 추가적으로 트리 순회할 때 dfs 돌면서 parent를 통해 순회여부를 판단하는 테크닉 사용
- visit 배열 선언할 필요가 없어서 일반적으로 공간복잡도에서 이득
- 스택에 로컬변수들 쌓이니까 일렬로 된 트리의 경우 다를바 없음.