4408. 자기 방으로 돌아가기

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWNcJ2sapZMDFAV8 

SW Expert Academy

 

분류

그리디

 

개인적 난이도

매우 쉬움

쉬움

보통

어려움

매우 어려움

 

핵심 알고리즘

방 번호를 낮은순으로 정렬하고 그리디 알고리즘을 활용해 한 번에 이동할 수 있는 학생들을 이동시킨다.

그 뒤 남은 학생들을 대상으로 반복한다.

room 2n-1번과 room 2n번은 사실상 동일한 이동선상에 있기 때문에

room id를 2로 나눈 값을 이용해 계산한다.

 

시행착오

문제에 설명이 다소 모호하여 처음 문제를 봤을 때 이해하기 위한 노력을 했어야 했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

int main(int c, char** v)
{
	int tc, T;

	scanf("%d", &T);

	for(tc = 1; tc <= T; ++tc){
		int N, cnt = 0;
		vector<pair<int, int> > arr;
		scanf ("%d", &N);

		for (int i = 0; i < N; i++){
			int x, y;
			scanf("%d %d", &x, &y);
			arr.push_back(make_pair((min(x, y) - 1) / 2, (max(x, y) - 1) / 2));
		}

		sort(arr.begin(), arr.end());

		while (!arr.empty()){
			int size = arr.size() - 1, max = arr.at(0).second;
			arr.erase(arr.begin());

			for (int i = 0; i < size; i++){
				if (arr.at(i).first <= max) continue;

				max = arr.at(i).second;
				arr.erase(arr.begin() + i);
				i--;
				size--;
			}

			cnt++;
		}

		printf("#%d %d\n", tc, cnt);
	}

	return 0;
}