[softeer] 업무처리

import sys

# input()을 ' '로 split, 이후 int로 mapping
height, job, day = map(int, input().split())
# print(height, job, day)

head_job = 0 # output, 보스가 처리한 일
all_node = 2 ** (height + 1) # 1부터 시작, 보스는 1
final_slave = (all_node) // 2   # 말단직원 수
slave = []
for i in range(all_node):
    if i > (final_slave - 1) :
        a = list(map(int, input().split()))
        slave.append(a)
    else :
        slave.append([])
# print(slave)

for i in range(1, 1 + day) : # day일 동안
    for j in range(height + 1) : # 전 직원을 층별로 순회
        if (height - j) % 2 == 0:
            for k in reversed(range(2 ** j)) :    # 각 층당 노드는 2**j개 존재
                idx = 2 ** j + k
                if len(slave[idx]) == 0 :    # 하나도 없으면 패스
                    continue
                if idx == 0:
                    did_job = slave[idx].pop(0)
                    head_job += did_job
                else :
                    cur_job = slave[idx].pop(0)
                    slave[idx//2].append(cur_job)
        else :
            for k in range(2 ** j) :    # 각 층당 노드는 2**j개 존재
                idx = 2 ** j + k
                if len(slave[idx]) == 0 :    # 하나도 없으면 패스
                    continue
                if idx == 0:
                    did_job = slave[idx].pop(0)
                    head_job += did_job
                else :
                    cur_job = slave[idx].pop(0)
                    slave[idx//2].append(cur_job)

print(sum(slave[0]))

상당히 어려웠다.

근데 어렵다는게, 문제를 이해하는게 어려웠다.

 

if (height - j) %2, else 부분을 제외하고는 금방 다 만들었는데, 이 조건문을 고안하는데만 꽤 걸렸다.

그니까, 제발 문제를 똑디 이해하고, 예제를 만들어 직접 풀어보면서 하자.

라고 하기엔... 나부터가 이해를 잘 못해서 예제를 직접 만들어도 그게 오답인지 몰랐다....

 

짝수번째 날짜엔 오른쪽 부하가 한 걸 처리하고,

홀수번째 날짜엔 왼쪽 부하가 한 걸 처리하는 걸 직접 손으로 하나하나 그려가면서 뭔지 이해했다.

 

if else 문의 차이는

range를 순방향으로 도냐, 역방향으로 도냐만 다르기에 이 부분은 함수 하나로 통합도 가능.

 

몇 번째 층에 있느냐에 따라, 일을 처리해야 하는 순서가 다르다.

즉, 1층은 오른쪽부터 일을 받아야 하며,

2층은 왼쪽부터 일을 받아야 함.

 

그러나 height는 위부터 순회해야 한다. 그렇지 않고 아래부터 순회하면,

아래로부터 일을 받은 다음 즉시 위로 가면서 위의 녀석도 일을 해버리게 됨.

받은 일을 그날 바로 처리하면 안 되기에, (height - j)에 따라 순회를 다르게 함으로써 처리함.