글 읽기 - c++ 86% 시간초과 어떻게 해야할지 모르겠습니다

mingu0217 1년 전 0

86%에서 시간초과가 나오는데 아무리 고민해봐도 더 개선할 수 있는게 없어보입니다...

혹시 개선사항에 대한 의견을 받을 수 있을까요?

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


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//하나씩 방을 만든다고 치고 그 방에서 하나씩 없애가면서 진행해야할듯
	//다 사라진 방에서 총 방의 개수 출력
	int num;
	cin >> num;
	vector<pair<int, int>> room;
	int n1, n2;
	for (int i = 0; i < num; ++i)
	{
		cin >> n1 >> n2;
		room.push_back(pair<int, int>(n1, n2));
	}
	//방에 입력 끝
	//일단 정렬
	sort(room.begin(),room.end());
	
	vector<int> now;
	now.push_back(-1);
    //방을 더해가면서 내부의 시간과 비교해 못들어가면 방 추가
	int size;
	int z;
	for(auto i:room)
	{
		size = now.size();
		for (z=0;z<size;++z)
		{
			if (i.first >= now[z])
			{
				now[z] = i.second;
				break;
			}
			
		}
		if (z == size)
		{
			now.push_back(i.second);
		}
	}
	
	cout << now.size();
	
}

mingu0217 1년 전 1

그냥 알고리즘 갈아엎으니까 되네요...

하나씩 비교하는게 아니라 가장 낮은 시간만 비교하면 됩니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 86% 시간초과 어떻게 해야할지 모르겠습니다

mingu0217 1년 전 0

mingu0217 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말