[백준OJ] 12978번 스크루지 민호 2

[백준OJ] 12978번 스크루지 민호 2

728x90

반응형

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

-풀이-

트리DP를 이용했다. dp[i][j]=k 라 할때, i번째 노드의 상태가 j일때( j==0 경찰서x / j==1 경찰서 o) 자식노드들과 자신을 포함하여 지어야할 경찰서의 최소개수가 k개라는것이다.

먼저 현재 노드에서 경찰서를 짓는다면, 자식노드들은 경찰서를 지어도되고, 안지어도된다.

만약 현재 노드에서 경찰서를 짓지 않는다면? 자식노드들은 무조건 경찰서를 지어야 한다.

이 두가지 경우를 이용하여 모든 경우의 수를 구해주는데, 매번 갱신을 할때마다 자식들을 하나하나 탐색을 한다면, 시간초과가 나므로, dp를 이용해서 시간복잡도를 줄여주었다.

-코드-

#include #include #include #define MAX 987654321 using namespace std; vector maze[100001]; int n; int dp[100001][2]; int dfs(int now, int parent, int isPolice) { if (dp[now][isPolice] != MAX) { return dp[now][isPolice]; } int police = 0; if (isPolice) police++;//자기자신노드에 경찰서가 있으면 개수+1 for (int next : maze[now]) { if (next != parent) { if (!isPolice) { //부모에 경찰서가 없으면, 자식은 무조건 경찰서가 있어야함. police += dfs(next, now, 1); } else { //부모에 경찰서가 있으면, 자식은 있는거 or 없는것 중 더 작은쪽을 택하면됨 police += min(dfs(next, now, 1), dfs(next, now, 0)); } } } //해당 경우의 최솟값을 저장 return dp[now][isPolice] = police; } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; maze[a].push_back(b); maze[b].push_back(a); } for (int i = 1; i <= n; i++) { dp[i][0] = dp[i][1] = MAX; } cout << min(dfs(1, 0, 0), dfs(1, 0, 1)); return 0; }

반응형

from http://khu98.tistory.com/213 by ccl(A) rewrite - 2021-08-01 18:26:44