백준 2533 - 사회 서비스(SNS)

백준 2533 - 사회 서비스(SNS)

https://www.acmicpc.net/problem/2533

★ 풀이

(얼리 아답터, 일반인) 이렇게 두 종류의 사람들이 있고, 일반인은 자신의 모든 친구들이 얼리 어답터일때만 정보를 받을 수 있을 때, 모든 사람이 정보를 공유하기 위해 필요한 얼리 아답터의 최소값을 구하는 문제이다. 어떻게 풀어야 할까 정말 고민을 많이 했다.

처음 생각했던 방식은 가장 leaf node 는 항상 일반인이라고 가정하고 (항상 부모 노드보다 같거나 많기 때문에), 부모노드는 자식 노드들 중에서 하나라도 일반인이 나온다면 얼리어답터로 계산하여 문제를 해결하려고 했다. 하지만 그것을 처리하기 위해 DFS로 구성을 해야했는데 생각보다 "자식 노드들 중에서 하나라도 일반인이 나온다면" 이라는 조건을 검사하기 복잡해져서 잠시 그 방법은 접어두었고, 보다 효율적이고 간단한 DP를 이용해서 풀었다.

DP를 이용한 풀이법은 각각의 경우가 독립적이기 때문에(겹치지 않는다.) 사용할 수 있었고, 중요한 포인트는 부모노드가 일반인인 경우 당연히 얼리어답터가 나와야하지만(일반인인 경우 모든 친구들이 얼리 어답터일때만 정보를 공유 받을 수 있기 때문에), 부모노드가 얼리어답터인 경우 자식노드는 일반인과 더불어 얼리어답터 또한 올 수 있다는 것이다.

부모노드가 얼리 어답터 일때 자식 노드도 얼리 어답터가 와야 최소값을 갖는 경우

★ 소스 코드

import java.io.*; import java.util.*; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int n; static int d[][]; static boolean visited[]; static ArrayList adj[]; public static void main(String[] args) throws IOException { n = Integer.parseInt(br.readLine()); adj = new ArrayList[n + 1]; for(int i = 1; i<=n; i++) { adj[i] = new ArrayList<>(); } d = new int[n + 1][2]; visited = new boolean[n + 1]; for(int i = 0; i 무조건 얼리어답터가 나와야함 d[x][1] += Math.min(d[next][0], d[next][1]); // 얼리 어답터인 경우 } return Math.min(d[x][1], d[x][0]); } }

from http://sweet-smell.tistory.com/46 by ccl(A) rewrite - 2021-09-13 22:00:24