[SWEA] 5178. 노드의 합

트리 문제를 이번 주 부터 시작 했는데 좀 어려웠다!!

 

이 문제는 리프노드에 숫자 데이터가 들어오고 각 부모 노드는 왼쪽자식 + 오른쪽 자식이다. 그래서 나는 반복문을 맨 끝에서 부터 돌았다. 2씩 줄게해서 부모 노드당 두개의 자식을 탐색하게 했다.

그림을 그려서 보니 인덱스 i라는 부모 노드가 존재하면 왼쪽 자식의 인덱스는 i*2이고 오른쪽 자식은 i * 2+1이다.

그래서 처음에 생각한 방법은 tree[i//2] = tree[i] + tree[i+1]이다. 그런데 인덱스 에러가 났다.

그림을 그려보니 노드의 개수가 짝수이면 맨 마지막에 왼쪽 노드만 존재하는 관계가 존재한다. 그래서 N이 짝수이면 맨 뒤 노드를 0이라는 데이터를 넣는 방식으로 내가 만들어서 넣었다. 그렇게 하면 부모= 왼 + 0 이 되므로 성립한다.

 

또 그렇게 하니까 인덱스 에러가떴다. ( tree[i//2] = tree[i] + tree[i+1] 이 부분에서 )

그래서 생각해낸 방법이 tree[i//2] = tree[i//2*2] + tree[i//2 *2 +1]이다.

---

# 3 : T
# 5 3 2 : N,M,L
# 4 1 : tree[4] = 1
# 5 2 : tree[5] = 2
# 3 3 : tree[3] = 3
# tree[2] = tree[4] + tree[5]
# tree[1] = tree[2] + tree[3] 인덱스*2 + 인덱스*2+1

T = int(input())

for tc in range(1, T+1):
    # 노드의 개수 N, 리프 노드의 개수 M, 값을 출력할 노드 번호 L
    N, M, L = map(int, input().split())
    # 왼쪽, 오른쪽, 부모
    tree = [[] for _ in range(N+1)] # 노드의 개수+1 만큼 트리를 만듦
    if N%2 ==0:
        tree.append(0)

    #리프노드 개수 만큼 반복문돌려 트리에 넣어줌
    for i in range(M):
        leaf, data = map(int, input().split())
        tree[leaf] = data

    for i in range(N,1,-2):
        tree[i//2] = tree[i//2*2] + tree[i//2*2 +1]

    print("#{} {}".format(tc, tree[L]))