문제

입력 , 출력

solution

import sys

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

n = int(input())
arr = [[],[0,0]]
arr2 = [[] for i in range(n + 2)]
res = 0
for i in range(1, n):
    t, a, p = input().split()
    a = int(a)
    p = int(p)
    arr.append([t, a, p])
    arr2[p].append(i + 1)


def dfs(now):
    scount = 0
    for i in arr2[now]:
        scount += dfs(i)
    if arr[now ][0] == 'S' and now != 1:
        scount += arr[now][1]
    elif arr[now][0] == 'W':
        scount = scount - arr[now][1]
    if scount <= 0:
        scount = 0
    return scount


res = dfs(1)
print(res)

설명

우선 간단한 ? DFS 문제이다. 리프 노드까지 내려가서 양이 몇마리가 올라오는지 체크를 하면 된다.
우선 리프노드까지 내려가서 양이면 부모노드에 올라가는 양을 return 해주고
양이 아닐경우에는 0 을 부모노드에 return 해준다.
해당 노드마다 자식노드에서 올라온 양이 몇마리인지 체크를 한다.
그리고 해당노드가 늑대이면 자식노드에서 올라온 양보다 늑대가 많으면
자신노드의 부모노드로 올라갈 양의 수를 0으로 return 해주고 양이 늑대보다 많으면 양의 수 - 늑대의 수 를 해줘서 부모노드에 return을 해준다.

후기

처음에는 늑대의수를 dfs로 내려가면서 없애는 방식으로 하니까 오류가 발생했다.
그래서 반대로 양의 수를 리프노드에서 올라가는 방식으로 하니 예제는 다 성공했는데 틀렸다고 나왔다. 한시간동안 머리를 굴리다가 다른사람의 코드를 보았는데 다른부분이 안보였다.
그래서 보니까 arr의 index 접근이 잘못되었다. arr에 접근을 할때
arr[now-2]로 접근을 했는데 0 , 1 번째 인덱스에 초기값을 넣어주고 index접근을 now로 바꾸니까 바로 맞았다.... 반례를 찾는데 도저히 생각이 안났는데 해보니 허무했다... index접근 하는것에 최대한 유의를 해야겠다.