[소프티어] 업무처리 (파이썬)

문제 - 업무처리 (★★★☆☆) 

Softeer

 

- 업무 조직도는 완전 이진트리 모양이다.

- 트리의 높이는 H, 말단에 대기하는 업무의 개수는 K, 업무가 진행되는 날짜 수는 R이다.

- 각 업무는 번호가 있다. 아래는 H = 1, K = 3인 조직도이다.

 

 

- 말단 직원들은 각각 K개의 순서가 정해진 업무를 가지고, 업무는 R일 동안 진행된다.

- 말단 직원은 업무를 하나씩 처리해서 상사에게 올리고, 다른 직원들도 마찬가지이다.

- 부하 직원에게 받은 업무는 다음 날에 처리하여 상사에게 올릴 수 있다. 즉, 당일 처리 X

- 이 때, 홀수 번째 날에는 왼쪽 부하가 올린 업무를, 짝수 번째 날에는 오른쪽  부하가 올린 업무만을 처리할 수 있다.

- 부서장(트리의 루트)이 처리한  일은 완료된 것이다.

- 이렇게 처리가 완료된 업무의 번호의 합을 구하는 문제이다.

 

풀이 방법

- 완전 이진트리의 특성을 이용. 

- 전체 직원의 수는 2^(H + 1) - 1이다. 

- 어떤 직원의 번호를 T라고 하자. T = 2라고 했을 때, T의 직속 부하의 번호는 (T*2, T*2+1)이 된다.

부서장(루트)의 번호가 1부터 시작한다고 가정하고 풀었는데 시작하는 번호에 따라서 값이 달라지기 때문에 주의.

- 처음엔 바텀-업(말단 직원 -> 부서장)으로 풀려고 했으나 "부하 직원에게 받은 업무는 다음 날 올릴 수 있다" 조건 때문에 트리를 업데이트 하기 복잡해져서 탑-다운(부사장->말단 직원)으로 풀이 방법을 전환.

- 부서장부터 시작하고, 직속 부하 직원이 업무를 가지고 있다면 처리가 완료된 업무이기 때문에 바로 올리면 된다. 이유는 로직대로 따라가보면 이해할 수 있음.

- R동안 반복하여 부서장까지 올라온 업무 중 처리된 업무 번호를 더하면 정답.

 

코드

from collections import deque

H, K, R = map(int, input().split())
works = [deque(map(int, input().split())) for _ in range(2**H)] # 처음 말단 직원의 업무
staffCount = 2**(H+1) - 1 # 전체 직원의 수
organization = [deque() for _ in range(staffCount+1)] # 1부터 처리하기 위해 +1 
for i in range(len(works)):
    organization[staffCount-i] = works[-i-1] # 말단 직원의 번호에 업무 할당
notEndStaff = 2**(H) # 말단 직원이 아닌 직원의 번호
complete = 0
for day in range(R):
    for t in range(1, notEndStaff): # 탑-다운 방식으로 진행되기 때문에 말단 직원 직전까지만 실행
        if t == 1:
            if len(organization[1]) != 0: # 부서장의 업무 중 처리된 업무가 있다면 그 번호를 더함
                complete += organization[1].popleft()
        if day % 2 == 1 : # 날짜가 홀수일 때
            if len(organization[t*2]) != 0:
                organization[t].append(organization[t*2].popleft())
        elif day % 2 == 0 : # 날짜가 짝수일 때
            if len(organization[t*2+1]) != 0:
                organization[t].append(organization[t*2+1].popleft())
        
print(complete)

 

문제 조건에서 1 <= R <= 1000 때문에 헷갈릴 수있는데 업무 날짜는 0부터 시작입니다. 

 

틀린 부분 지적이나 조언 환영합니다!