문제

https://softeer.ai/practice/6251

---

입력

첫 줄에 조직도의 높이 H, 말단에 대기하는 업무의 개수 K, 업무가 진행되는 날짜 수 R이 주어진다.
그 다음 줄부터 각각의 말단 직원에 대해 대기하는 업무가 순서대로 주어진다.
제일 왼쪽의 말단 직원부터 순서대로 주어진다.

---

출력

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

---

풀이

제한조건

• 1 ≤ H ≤ 10
• 1 ≤ K ≤ 10
• 1 ≤ R ≤ 1,000

접근방법

일종의 시뮬레이션 문제이다.
근데 이제 트리구조를 곁들인.

문제에서 조직의 구조가 완전 이진트리를 이룬다고 한다.

편의를 위해서 가장 상단 노드를 1로 두고 번호를 부여해보자.
그럼 루트노드(부서장), 중간 노드(중간 직원), 리프 노드(말단 직원)의 번호가 몇부터 시작하는 지 알 수 있다.

 int N = 1 << (H+1); // 전체 노드의 수
 int leaf = 1 << H; // 말단 직원중 가장 낮은 번호

트리 구조를 잡았으니 이제 업무 처리에 대해서 생각해보자.

각 직원은 업무를 가지고 있다.
또한 업무의 순서가 정해져 있고 순서대로 진행하므로,
각 직원에게 Queue를 만들어 두고 진행한다.

여기서 문제의 조건에 따라 홀-짝 날짜에 따라 처리하는 업무가 정해져 있으므로 각 직원에게 2개읭 Queue를 만들어주자.

Queue<Integer>[][] task = new Queue[2][N];

이제 구조적인 부분이 모두 해결되었다.
날짜를 흘려보내며, 업무를 처리해보자.

1. 부서장이 업무를 먼저 처리한다.
(부하 직원이 올린 업무는 그 다음날 처리되므로)
2. 중간 직원들의 업무를 처리한다.
3. 말단 직원들의 업무를 처리한다.

트리 구조를 잡고, 각 직원마다 작업큐를 2개씩 할당해야겠다.
라는 생각을 했다면 문제를 다 풀었다고 볼 수 있다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
    static int H, K, R;
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = in.readLine().split(" ");
        H = stoi(inputs[0]);
        K = stoi(inputs[1]);
        R = stoi(inputs[2]);

        int N = 1 << (H+1); // 전체 노드의 수
        Queue<Integer>[][] task = new Queue[2][N];
        for(int i = 0 ; i < 2; ++i)
            for(int j = 0; j < N; ++j)
                task[i][j] = new ArrayDeque();

        int leaf = 1 << H; // 말단 직원중 가장 낮은 번호
        for(int i = leaf; i < leaf * 2; ++i){
            inputs = in.readLine().split(" ");
            for(int j = 0; j < K; ++j)
                task[0][i].add(stoi(inputs[j]));
        }

        int result = 0;
        for(int day = 1; day <= R; ++day){
            int bit = day % 2;
            // bit : 1, 홀수 일
            // bit : 0, 짝수 일

            // 부서장
            if(!task[bit][1].isEmpty())
                result += task[bit][1].poll();
            
            // 일반 직원
            for(int i = 2; i < leaf; ++i){
                int parent = i / 2;
                if(task[bit][i].isEmpty())
                    continue;
                task[(i+1)%2][parent].add(task[bit][i].poll());
            }

            // 말단 직원
            for(int i = leaf; i < leaf * 2; ++i){
                int parent = i / 2;
                if(task[0][i].isEmpty())
                    continue;
                task[(i+1)%2][parent].add(task[0][i].poll());
            }
        }
        System.out.println(result);
    }

    public static int stoi(String s){
        return Integer.parseInt(s);
    }
}