https://softeer.ai/practice/info.do?idx=1&eid=1256

설계

# tree dictionary matrix update
day = 1
while day <= R:
    # 부서장
    if tree_matrix[0]['L'] and day%2:
        answer += tree_matrix[0]['L'].popleft()
    if tree_matrix[0]['R'] and not day%2:
        answer += tree_matrix[0]['R'].popleft()
    
    # 중간급 직원
    for i in range(1,node-2**H):
        if day%2 and i%2 and tree_matrix[i]['L']:
            tree_matrix[(i-1)//2]['L'].append(tree_matrix[i]['L'].popleft())
        if day%2 and not i%2 and tree_matrix[i]['L']:
            tree_matrix[(i-1)//2]['R'].append(tree_matrix[i]['L'].popleft())
        if not day%2 and i%2 and tree_matrix[i]['R']:
            tree_matrix[(i-1)//2]['L'].append(tree_matrix[i]['R'].popleft())
        if not day%2 and not i%2 and tree_matrix[i]['R']:
            tree_matrix[(i-1)//2]['R'].append(tree_matrix[i]['R'].popleft())
    # 말단 노드
    for i in range(node-2**H,node):
        if tree_matrix[i] and i%2:
            tree_matrix[(i-1)//2]['L'].append(tree_matrix[i].popleft())
        if tree_matrix[i] and not i%2:
            tree_matrix[(i-1)//2]['R'].append(tree_matrix[i].popleft())
    day += 1

• tree_matrix: dictionary로 이루어진 2차원 배열이다. dictionary는 'L'과 'R'로 나뉘며 각각 왼쪽에서 올라온 업무, 오른쪽에서 올라온 업무를 뜻한다.

Ex) tree_matrix = [ {'L':[], 'R':[]}, {'L':[1,2], 'R':[4]}, {'L':[5,7,8], 'R':[]}]

3일 차(홀수)에 처리할 수 있는 업무는

1번 노드에서 "1,2" 업무, 2번 노드에서 "5,7,8" 업무를 처리할 수 있다.

이 tree_matrix를 문제 조건에 맞추어 계속 갱신시키며 문제를 푼다.

1. 순서는 부서장,중간 직원, 말단 직원 순으로 업데이트를 한다. 왜냐하면, 모든 업무 보고는 동시에 일어나기 때문이다.

2. 부서장(루트 노드)은 홀수일 때 'L'/ 짝수일 때 'R'에서 원소를 꺼내어 답에 누적시킨다.

3. 중간 직원은 각 케이스에 따라 업무 보고를 한다.

3-1. 날짜가 홀수 / 노드 위치가 왼쪽
3-2. 날짜가 홀수 / 노드 위치가 오른쪽
3-3. 날짜가 짝수 / 노드 위치가 왼쪽
3-4. 날짜가 짝수 / 노드 위치가 오른쪽

4. 말단 직원은 날짜에 관계없이 업무보고를 하므로 노드 위치만 구분 지어 원소를 꺼낸다.

코드

import sys
from collections import deque
input = sys.stdin.readline
answer = 0
# node number
def cal_node(H):
    node = 1
    for i in range(H):
        node += 2**(i+1)
    return node

# Input
H,K,R = map(int,input().split())
node = cal_node(H)
tree_matrix = [dict({'L': deque([]),'R':deque([])}) for _ in range(node)]
for i in range(node-2**H,node):
    tree_matrix[i] = deque(list(map(int,input().split())))

# tree dictionary matrix update
day = 1
while day <= R:
    # 부서장
    if tree_matrix[0]['L'] and day%2:
        answer += tree_matrix[0]['L'].popleft()
    if tree_matrix[0]['R'] and not day%2:
        answer += tree_matrix[0]['R'].popleft()
    
    # 중간급 직원
    for i in range(1,node-2**H):
        if day%2 and i%2 and tree_matrix[i]['L']:
            tree_matrix[(i-1)//2]['L'].append(tree_matrix[i]['L'].popleft())
        if day%2 and not i%2 and tree_matrix[i]['L']:
            tree_matrix[(i-1)//2]['R'].append(tree_matrix[i]['L'].popleft())
        if not day%2 and i%2 and tree_matrix[i]['R']:
            tree_matrix[(i-1)//2]['L'].append(tree_matrix[i]['R'].popleft())
        if not day%2 and not i%2 and tree_matrix[i]['R']:
            tree_matrix[(i-1)//2]['R'].append(tree_matrix[i]['R'].popleft())
    # 말단 노드
    for i in range(node-2**H,node):
        if tree_matrix[i] and i%2:
            tree_matrix[(i-1)//2]['L'].append(tree_matrix[i].popleft())
        if tree_matrix[i] and not i%2:
            tree_matrix[(i-1)//2]['R'].append(tree_matrix[i].popleft())
    day += 1
# Output
print(answer)