[Softeer] HSAT 5회 기출 - 업무 처리

문제

<배경>

어떤 부서의 업무 조직은 완전이진트리 모양이다.

즉, 부서장이 루트이고 부서장 포함 각 직원은 왼쪽과 오른쪽의 부하 직원을 가진다. 부하 직원이 없는 직원을 말단 직원이라고 부른다.

 

모든 말단 직원은 부서장까지 올라가는 거리가 동일하다. 조직도 트리의 높이는 $H$이다. 아래는 높이가 1이고 업무가 3개인 조직도를 보여준다.

업무는 $R$일 동안 진행된다. 처음에 말단 직원들만 각각 $K$개의 순서가 정해진 업무를 가지고 있다.

각 업무는 업무 번호가 있다. 각 날짜에 남은 업무가 있는 경우, 말단 직원은 하나의 업무를 처리해서 상사에게 올린다.

다른 직원들도, 대기하는 업무가 있는 경우 업무를 올라온 순서대로 하나 처리해서 상사에게 올린다.

단, 홀수 번째 날짜에는 왼쪽 부하 직원이 올린 업무를, 짝수 번째 날짜에는 오른쪽 부하 직원이 올린 업무를 처리한다.

 

부서장이 처리한 일은 완료된 것이다. 업무를 올리는 것은 모두 동시에 진행한다.

따라서 그날 올린 업무를 상사가 처리하는 것은 그 다음날에야 가능하다.

 

부서의 조직과 대기하는 업무들을 입력 받아 처리가 완료된 업무들의 번호의 합을 계산하는 프로그램을 작성하라.

 

<입력>

 

<출력>

완료된 업무들의 번호 합을 정수로 출력한다.

---

풀이

문제 이해는 어렵지 않다.

직원들이 자신의 상사한테 업무를 하나씩 올릴 때 부서장이 처리한 일이 어떤건지 확인하는 것이다.

 

 

말단 직원들은 할 일의 번호를 리스트로 가지고 있을 것이므로, 한 층 높은 계급의 사람은 자신의 양쪽 직원이 가진 리스트를 하나씩 하나씩 번갈아가며 취해 본인의 리스트로 만들면 된다.

sort는 아니지만 merge sort와 비슷한 구조라고 생각하면 된다.

다만 신경써야하는 부분은 홀수,짝수 날짜에 따라 먼저 시작하는 순서가 달라진다는 것이다.

추가로 부서장은 말단으로부터 본인에게 업무가 올라올 초반 며칠동안은 일을 하지 않는다는 것이다.

이를 고려해 정답을 출력해주면 된다.

h,k,r = map(int,input().split())

tasks = []
for _ in range(2**h):#완전이진트리의 leaf 노드 개수
    tasks.append(list(map(int,input().split()))) 

for i in range(1,h+1):
    tasks2 = [] #merge한 결과
    for j in range(2**(h-i)): #2개씩 짝 지었을 때 나오는 쌍 개수
        if i%2:
            tasks2.append(merge(tasks[j*2+1],tasks[j*2]))
        else:
            tasks2.append(merge(tasks[j*2],tasks[j*2+1]))
    tasks = tasks2

print(sum(tasks[0][:r-h])) #h동안은 부서장 일 없음

def merge(lst1,lst2):
    lst = []
    for i in range(len(lst1)):
        lst.append(lst1[i])
        lst.append(lst2[i])
    return lst