[BOJ] 16437 : 양 구출 작전 (C++)

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

걸린 시간 : 24분

---

골드3이 맞나... 싶은 문제.

알고리즘

루트(1번 섬)부터 시작해서 자식들로부터 오는 양의 수를 세면 된다.

dfs(int k) 메소드는 k번째 섬에 오는 양의 수이다. 만약 늑대가 다 먹어서 다 못 온다면 0이 오게 될 것이다.

정답 코드

#include <bits/stdc++.h>
using namespace std;

int N;
long long island[123457];
vector<int> children[123457];
bool kind[123457];

long long dfs(int k) {
	if (kind[k]) {
		long long ret = island[k];
		for (int c : children[k]) {
			ret += dfs(c);
		}
		return ret;
	}
	else {
		long long ret = -island[k];
		for (int c : children[k]) {
			ret += dfs(c);
		}
		return max((long long)0, ret);
	}
	
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 2; i <= N; i++) {
		char t;
		long long a;
		int p;
		cin >> t >> a >> p;
		kind[i] = t == 'S';
		children[p].push_back(i);
		island[i] = a;
	}
	long long answer = 0;
	for (int c : children[1]) {
		answer += dfs(c);
	}
	cout << answer;
	return 0;
}