취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 27112번 문제인 시간 외 근무 멈춰!이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/27112 

주어지는 N개의 작업을 마감기한이 다가오는 순서, 즉 d값이 오름차순인 순서대로 작업하는 것으로 항상 최적해를 구할 수 있음은 쉽게 관찰할 수 있다. 평시 근무가 가능한 잔여 날의 수와 시간 외 근무가 가능한 잔여 날의 수를 관리 및 유지해 문제를 해결해보자.

글쓴이는 d의 값이 10만 이하이므로, 하루하루가 지나는 것을 직접 시뮬레이션하며 월~금요일일 경우 평시 근무 가능 시간 1과 시간 외 근무 가능 시간 1을, 토~일요일일 경우 시간 외 근무 가능 시간 1만을 늘려나가는 식으로 근무 시간을 관리해 문제를 해결하였다. 이는 아래 코드와 같이 근무 일수를 7로 나눈 나머지를 이용해 깔끔하게 구현할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
pair<int, int> work[100000];
int daycnt, x, y;
int ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int n = 0; n < N; n++) {
		cin >> work[n].first >> work[n].second;
	}
	sort(work, work + N);

	for (int n = 0; n < N; n++) {
		while (daycnt < work[n].first) {
			if (daycnt % 7 < 5) x++;
			y++, daycnt++;
		}
		if (x >= work[n].second) x -= work[n].second;
		else if (x + y >= work[n].second) {
			int tmp = work[n].second - x;
			x = 0, y -= tmp, ans += tmp;
		}
		else {
			cout << -1;
			return 0;
		}
	}

	cout << ans;
}