백준 27112 - 시간 외 근무 멈춰!(C++)

문제 링크입니다. https://www.acmicpc.net/problem/27112

27112번: 시간 외 근무 멈춰!

정렬을 이용한 문제입니다.

일의 마감시한과 걸리는 시간이 주어졌을 때, 이를 끝낼 수 있는지를 구하는 문제입니다.

 

일을 끝내긴 위해선 먼저 마감기한이 빠른 일부터 끝내야합니다.

따라서 정렬을 해야하는데, 데이터 값이 2개가 있습니다. 마감기한과 걸리는 시간입니다.

마감기한이 우선이기에 마감기한 -> 걸리는 시간 순으로 우선순위를 정해서 정렬을 해주면 됩니다.

 

정렬을 마쳤으면, 일을 끝낼 수 있는지를 구해야합니다.

저는 마지막 기한일을 저장해 1일부터 for문을 돌렸습니다.

 

주말은 하루, 평일은 2일을 일할 수 있습니다.

그래서 변수를 통해 하루가 지날 때마다, 일을 끝낼 수 있는 날을 증가해줬습니다.

for문에서 근무의 마감일을 만나면, 저장한 변수를 통해 해당 일을 끝낼 수 있는지를 확인했습니다.

이때, while문을 사용했는데 이는 같은 기한을 가진 일이 있을 수 있기 때문입니다.

 

문제에서 원하는 것은 최소의 시간 외 근무입니다.

따라서 저는 평시 근무, 시간 외 근무를 따로 저장해줬습니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#define P pair<int,int>
#define PP pair<P, int>
#define F first
#define S second
#define LL long long

using namespace std;

int N;
vector<P> work;

bool cmp(P a, P b){
    if(a.F < b.F) return true;
    else if(a.F == b.F){
        if(a.S < b.S) return true;
        else return false;
    }
    else return false;
}

int can_fin(){
    int work_time = 0, start = 0, plus_time = 0;
    sort(work.begin(), work.end(), cmp);
    int Fin = work[work.size() - 1].F;
    for(int i = 1; i <= Fin; i++){
        if(i%7 == 0 || i%7 == 6) plus_time += 1;
        else{
            work_time += 1;
            plus_time += 1;
        }
        while(1){
            if(work[start].F == i){
                if(work[start].S <= work_time){
                    work_time -= work[start].S;
                    start++;
                }
                else if(work[start].S - work_time <= plus_time){
                    plus_time -= (work[start].S - work_time);
                    work_time = 0;
                    start++;
                }
                else return -1;
            }
            else break;
        }
    }
    return Fin - plus_time;
}

void solve(){
    cout << can_fin();
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 0; i < N; i++){
	    int x, y;
	    cin >> x >> y;
	    work.push_back({x, y});
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요