문제 URL : https://www.acmicpc.net/problem/16437
16437번: 양 구출 작전
2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로
www.acmicpc.net
문제 접근법 :
처음 풀었을때 루트에서 시작해서 모든값을 다더하는 줄 알았습니다. 그렇게되면 해당 노드에서 자식노드로 더하게된다면 해당 양은 분신술을 쓰거나 ,늑대는 1마리이상 잡아먹는꼴이므로 답이 될수없지요
반드시 늑대가 1마리를 잡아먹게 할려면

이그림을 잘볼때 leap노드에서 부모로 더해준다면

반드시 한마리만 잡아먹도록 할수있습니다. 그리고 만약 자기자신의 노드가 음수라면 해당 자식노드의 양들은 더이상 루트노드로 움직일수 없다는것을 알수있기때문에 리프에서부터 루트노드로 해당값을 더해주면됩니다.
그래프 또한 단방향 트리이면 충분히 풀수있습니다.
소스코드 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> v[123457];
ll sum[123457];
int n;
void dfs(int cur=1,int before=0) {
for (int i = 0; i < v[cur].size(); i++) {
dfs(v[cur][i], cur);
}
if (sum[cur] > 0)//현재 양만 존재해야함
sum[before] += sum[cur];//현재의 가치를 부모노드가 물려받음
}
void input() {
char c;
int a, p;
cin >> n;
for (int i = 2; i <= n; i++) {
cin >> c >> a >> p;
a = (c == 'S' ? a : -a);//양이면 양수 늑대면 음수
v[p].push_back(i);//단방향 트리
sum[i] = a;
}
}
void solve() {
dfs();
cout << sum[1] << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
백준 16637 괄호 추가하기 (0) | 2022.05.17 |
---|---|
백준 17472 다리 만들기 2 (0) | 2022.05.17 |
백준 2688 줄어들지 않아 (0) | 2022.04.07 |
백준 1103 게임 (0) | 2022.04.07 |
백준 20005 보스몬스터 전리품 (0) | 2022.03.30 |