Softeer [HSAT 5회 정기 코딩 인증평가 기출] 업무 처리(c++)

문제 URL : https://www.softeer.ai/practice/6251#pop_user

Softeer - 현대자동차그룹 SW인재확보플랫폼

문제 접근법 :  

이진트리를 배열을 이용해서 구현할줄 아는지 묻는문제고

포화이진트리의 개념을 물으면서 q를 이용하는 문제이니다.

 

현재 노드를 i라고할때 왼쪽자식 i*2, 오른쪽 자식은 i*2+1 입니다. 물론 루트가 1이라는 가정하에서

모든노드를 q로 구성하고 리프노드의 업무를 vector로 입력받습니다.

 

매일 하나의 업무를 처리하고나면 자신의 해당하는 q노드에 업무를 넣어놓고

day때마다 상사가 홀수날이면 왼쪽자식에서 있는큐를 자신의 큐로 , 짝수날이면 오른쪽 자식에 있는큐를 자신의 큐에 담는게 핵심입니다.

 

업무처리날짜까지 전부 업무를 처리했을때 q[1]에해당하는 모든 값을 더해주면 되는겁니다.

 

소스코드:

 

 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll h,k,r;
queue<ll>q[1<<13];
vector<ll> v[1<<13];
void input(){
    cin>>h>>k>>r;
    ll a;
    for(int i =1<<h;i<(1<<(h+1));i++){
        for(int j=0;j<k;j++){
            cin>>a;
            v[i].push_back(a);
        }
    }
}
void solve(){
    ll res = 0;
    ll day=0;
    while(day<r){
        for(int i=1;i<(1<<h);i++){
            if(!q[i*2+day%2].empty()){
                ll val = q[i*2+day%2].front();
                q[i*2+day%2].pop();
                q[i].push(val);
            }
        }
        for(int i =1<<h;i<(1<<(h+1));i++){
            if(day<v[i].size()){
                q[i].push(v[i][day]);
            }
        }
        day++;
    }
    while(!q[1].empty()){
        res +=q[1].front();
        q[1].pop();
    }
    cout<<res<<"\n";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    input();
    solve();
}

 

궁금한점 혹은 모르는점 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.