[BOJ] 1949 우수 마을

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

1949번: 우수 마을

문제

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개 줄에 걸쳐서 인접한 두 마을의 번호가 빈칸을 사이에 두고 주어진다.

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

출력

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

14000

---

아까 풀었던 SNS 문제랑 상당히 비슷한 문제였다.

조건이 몇개 더 있어서 수정할 것이 많다고 생각했는데

고쳐놓고 보니 min에서 max로 바꾼 것 밖에 다르지 않았다.

 

이번엔 1이 우수 마을로 선정된 경우, 0이 우수 마을로 선정되지 않은 경우로 설정했다.

 

 

입력 예시 (1, 3, 5, 7번 마을 선정)

 

문제의 3번 조건 때문에 이번 마을이 선정되지 않는다면 자식 마을이 선정돼야 한다고 생각해서

27번째 줄에서 처음엔 max를 사용하지 않고 dp[child][1]만 더 했었다.

그랬더니 답이 11000이 나왔다.

 

곰곰히 생각해보니 자식 마을의 자식 마을이 선정되는 경우엔 크게 상관이 없어 보였다. 

따라서 자식 마을이 선정되지 않은 경우엔 자식 마을의 자식 마을이 선정됐을것 이므로 max를 사용했다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 10001

int N;
int u, v;
vector<int> edge[MAX];
int p[MAX];
int dp[MAX][2];
bool visited[MAX];

void find(int x) {
	visited[x] = true;
	dp[x][1] = p[x];

	for (int i = 0; i < edge[x].size(); i++) {
		int child = edge[x][i];
		if (visited[child]) continue;
		find(child);

		dp[x][1] += dp[child][0];
		dp[x][0] += max(dp[child][1], dp[child][0]);
	}
}

int main() {
	scanf("%d", &N);

	for (int i = 1; i <= N; i++)
		scanf("%d", &p[i]);

	for (int i = 0; i < N - 1; i++) {
		scanf("%d %d", &u, &v);
		edge[u].push_back(v);
		edge[v].push_back(u);
	}

	find(1);

	printf("%d\n", max(dp[1][0], dp[1][1]));

	return 0;
}

 

후기)

트리 DP는 이제 까먹지만 않는다면 풀 수 있을 것 같다!