#20126

• 문제

안형찬 교수님은 알고리즘 분석 기말고사를 준비하려고 한다.

알고리즘 기말고사는 총 M분 동안 쉬는 시간 없이 볼 예정이며, 인원이 너무 많아서 공학관 C040호에서 말고 다른 강의실에서 시험을 치를 수 없게 되었다.

공학관 C040호는 0분부터 S분까지 사용 가능하다. S는 무조건 M 이상이기 때문에 안 교수님은 별문제 없이 시험을 치를 것으로 생각하였다. 그러나 공학과 C040호에는 다른 시험도 예정되어 있어서 겹치지 않는 시간을 잡아야 한다.

각 시험은 xi분에 시작해서 yi분 동안 진행하며 서로 겹치지 않는다. 한 시험이 끝난 직후 다음 시험이 있는 경우도 겹치지 않는 것으로 판단한다. 즉, xi + yi ≤ xj 일 때 i 시험과 j 시험은 서로 겹치지 않는다.

안형찬 교수님이 시험을 언제 치를 수 있는지 구해보자.

• 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int availTime(vector<vector<int>>& arr, int n, int m, int s) {
	int t = -1;

	if (arr[0][0] != 0 && m <= arr[0][0]) {
		return 0;
	}

	for (int i = 0; i < n; i++) {
		if (i == n - 1) {
			if ((arr[n - 1][1] + m) <= s) {
				t = arr[n - 1][1];
			}
			break;
		}

		if (arr[i + 1][0] >= (arr[i][1] + m)) {
			t = arr[i][1];
			break;
		}

	}

	return t;
}

int main()
{
	int n, m, s;
	int x, y;


	//입력
	cin >> n >> m >> s;

	vector<vector<int>>arr(n, vector<int>(2, 0));




	for(int i = 0; i < n; i++) {

		//시험 시간 입력
		cin >> x >> y;
		arr[i][0] = x;
		arr[i][1] = x + y;
	}

	//x순으로 정렬 
	sort(arr.begin(), arr.end());

	//연산
	
	cout << availTime(arr, n, m, s);

}

• 해설

1. availTime(vector<vector<int>>& arr, int n, int m, int s)

- 시험 가능한 시간을 연산하는 함수

: 시험 가능한 시간을 표현하는 변수 t를 -1로 초기화

: 만약 x1이 0이 아니고 x1이 시험 보는 시간인 m보다 크거나 같다면, 즉 초반에 시간이 빈다면 0을 return

: 중간에 시간이 비는 경우, for문을 통해 n 번의 연산을 반복

: 만약 i가 n-1이라면 n-1번째에 해당하는 시험의 끝나는 시간에 m을 더한 것이 시험장을 최종적으로 쓸 수 있는 시간인 s보다 작거나 같다면, 즉 맨 후반에 시간이 빈다면 n-1번째에 해당하는 시험의 끝나는 시간을 return

: 만약 그것이 아니라면 i번째에 해당하는 시험의 끝나는 시간에 m을 더한 것이 i+1번째에 해당하는 시험의 시작 시간보다 작거나 같다면 i번째에 해당하는 시험의 끝나는 시간을 return

 

2. main 함수

: n, m, s를 각각 입력 받음

: 각 시험의 시작 시간과 끝나는 시간을 저장할 2차원 벡터 arr 선언

: for문을 통해 x,y를 입력 받고 arr[i][0]에는 x, arr[i][1]에는 x+y를 대입해 시험의 시작시간과 끝나는 시간을 저장

: sort함수를 통해 arr[i][0]을 기준으로 arr의 원소를 정렬

: availTime 함수를 통해 t를 연산하여 출력