[백준][다이나믹] 2533 사회망 서비스

다이나믹을 이용하여 해결할 수 있다. 

자신이 얼리어답터일 때와 아닐때를 구분하여, 관계를 더하여 가면 해결할 수 있다. 

	package sdk.backjun.dp;
	import java.util.LinkedList;
	import java.util.Scanner;
	/**
	* 백준, 2533, 다이나믹 프로그래밍
	* 사회망 서비스(SNS)
	*
	* @author whitebeard-k
	*
	*/
	public class Problem2533 {
	static int N;
	static int[] visit;
	static int[][] dp;
	static LinkedList<Integer>[] list;
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	N = sc.nextInt();
	visit = new int[N + 1];
	dp = new int[N + 1][2];
	list = new LinkedList[N + 1];
	for (int i = 1; i <= N; i++)
	list[i] = new LinkedList<>();
	for (int i = 0; i < N - 1; i++) {
	int a = sc.nextInt();
	int b = sc.nextInt();
	list[a].add(b);
	list[b].add(a);
	}
	int start = 1;
	dfs(start);
	System.out.println(Math.min(dp[start][0], dp[start][1]));
	}
	public static void dfs(int index) {
	visit[index] = 1;
	dp[index][0] = 0;
	dp[index][1] = 1;
	LinkedList<Integer> item = list[index];
	for (int to : item) {
	if (visit[to] == 0) {
	dfs(to);
	dp[index][0] += dp[to][1];
	dp[index][1] += Math.min(dp[to][0], dp[to][1]);
	}
	}
	}
	}

view raw Problem2533.java hosted with ❤ by GitHub