BOJ(C++) / 백준 6068 : 시간 관리하기

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

6068번: 시간 관리하기

문제

성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1<=N<=1000) 숫자를 매겼다. (우유를 짜고, 마굿간을 치우고, 담장을 고치는 등의)

존의 시간을 효율적으로 관리하기 위해, 그는 끝내야만 하는 일 목록을 만들었다. 완성될 때 필요한 시간을 T_i(1<=T_i<=1,000) 라고 하며, 끝내야하는 시간을 S_i(1<=S_i<=1,000,000) 이라 한다. 농부 존은 하루의 시작을 t = 0으로 정했다. 그리고 일 할 때는 그 일을 마칠 때 까지 그 일만 한다. 

존은 늦잠 자는 걸 좋아한다. 따라서 제 시간에 끝낼 수 있게 결정할 수 있는 한도에서 존이 가장 늦게 일어나도 되는 시간을 출력하라.

입력

첫 줄에는 일의 개수인 N을 받고

두 번째 줄부터 N+1줄까지 T_i와 S_i를 입력받는다. 

 

출력

존이 일을 할 수 있는 마지막 시간을 출력 하라. 존이 제시간에 일을 끝낼 수 없다면 -1 을 출력하라.

---

문제 풀이

정렬, 그리디 알고리즘을 사용하였다.

우선은 끝나는 시간이 이른 순서대로 주어진 값들을 정렬하여야 한다.

빨리 끝나는 일부터 차례대로 진행하면서 시간 내에 끝낼 수 있는지 없는지 판별하고, 끝낼 수 있다면, 얼마나 여유시간이 있는지까지 판별해야 하는 문제이다.

여유시간을 구하는 방법은 다음과 같다.

 

1. T_i =3, S_i=6

full

full

full

2. T_i=4,S_i=5

full

full

full

full

3. T_i=2, S_i=7

full

full

위와 같이 3개의 task가 주어졌다면, 각 시간에 맞게 앞에서부터 우선적으로 일을 하며 시간을 채워간다고 생각한다.

그 후 3개의 일과들을 모두 한 칸씩 민다고 할 때, 다 같이 밀 수 있는 칸의 수가 최대 여유시간이다.

위의 경우에는 task2 때문에 최대 한 칸만 밀 수 있으므로 최대 여유시간은 1이 된다.

코드를 보자.

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

int N,Ti,Si;

vector<pair<int,int>> ts;

bool compare(pair<int,int> a,pair<int,int> b){
	return a.second<b.second;
}

int main(){
	int min_dif=99999999;
	int time=0;
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>Ti>>Si;
		ts.push_back(make_pair(Ti,Si));
	}
	sort(ts.begin(),ts.end(),compare);
	for(int i=0;i<N;i++){
		
		Ti=ts[i].first;
		time+=Ti;
		Si=ts[i].second;
		min_dif=min(min_dif,(Si-time));
		
	}
	if(min_dif<0){
		cout<<-1;
	}
	else{
		cout<<min_dif;
	}
}