[ICPC] Working Plan

백준 16368번으로 풀어본 icpc 문제

 

해결해야 할 일과 일들을 할 사람들이 존재하는 상황에서

일을 끝내기 위해 며칠에 몇시간의 일을 해야하는 지와 각 사람들이 총 몇시간 일할수 있는지가 주어진다

또한 사람들은 한번에 며칠을 연속으로 일해야하고 일한 후에는 며칠을 쉬어주어야한다

이 때 가능한 방법이 있으면 1과 어떻게 사람을 배치해야 하는지 없다면 -1을 출력해야한다

 

가능한 방법이 있는 경우 원래 일보다 추가로 일해도 되는지가 문제 해석 중 헷갈렸지만 고려하지 않아도 정답인정이 되었다

 

#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
 
int Person[2005];
vector<pair<pair<int, int> ,int> > status; // remain, day, people
vector<int> ans[2005];
int Days[2005];
 
int main(){
    int m,n,h,w;
    scanf("%d %d %d %d",&m,&n,&w,&h);
    for(int i = 1 ; i <= m ; i++){
        int tmp;
        scanf("%d",&tmp);
        status.push_back(make_pair(make_pair(-tmp,1),i));
    }
    for(int i = 1 ; i <= n ; i++) scanf("%d", &Days[i]);
 
    for(int i = 1 ; i <= n ; i++){
        int remained,start,people,idx,len=status.size();
        sort(status.begin(),status.end());
 
        for(idx = 0 ; idx != len ; idx++){
            if(Days[i]<=0) break;
            start = status[idx].first.second;
            if(start<=i){
                remained = status[idx].first.first*-1;
                people = status[idx].second;
                ans[people].push_back(i);
                for(int j = i ; j < i + w ; j++){
                    Days[j]--;
                }
                if(remained-w>0){
                    status[idx].first.first= (remained-w)*-1;
                    status[idx].first.second = i+w+h;
                }
                else{
                    status[idx].first.second = 2005;
                }
            }
            
        }
        if(Days[i]>0){
            printf("-1\n");
            return 0;
        }
    }
    printf("1\n");
    for(int i = 1 ; i <= m ; i++){
        for(auto it = ans[i].begin() ; it!= ans[i].end() ; it++){
            printf("%d ",*it);
        }
        printf("\n");
    }
}

 

그리디를 생각하면서 풀었는데 처음에는 가장 일을 빨리 시작할 수 있는 사람으로 잘못 풀었다ㅠㅠ

일을 빨리 시작할 수 있는 사람이 아니라 앞으로 가장 많은 시간을 일 할 사람을 먼저 일을 시켜야했다

status라는 벡터에 각 사람들의 남은시간과 일 그리고 정답 벡터를 만들기 위해서 필요한 worker index를 저장하였다

각 날짜별로 정답을 저장하는 벡터배열을 만들었다

문제 해결을 위해 가장 바깥 for문은 각 날짜를 확인하였다

매번 반복을 위해 status를 먼저 정렬시켰다

정렬이 되었으므로 가장 해야할 일이 많이 남은 사람이 vector의 앞에 위치하게 된다

하지만 가장 해야할 일이 많이 남은 사람이 꼭 그 날짜에 일할 수 있는 것은 아니므로 start가 해당 날짜보다 작은 경우에만 일을 시작하도록 했다

일을 시작하면 날짜에 진행해야 하는 양을 줄여주고 그 사람이 할 수 있는 일의 양도 줄여준다

더이상 일을 할 수 없다면 start day를 2005로 지정해주어 최대 날짜 2000을 넘기도록 하였다

해당 날짜의 일이 종료되면 break 후 다음날짜로 넘어간다

모든 사람을 확인했는데 특정 날짜의 일을 끝낼 수 없는 경우 -1 출력후 종료, 모든 일을 끝냈다면 벡터배열을 출력 후 종료한다