글 읽기 - 시간복잡도 및 시간초과에 대하여 도움 요청드립니다.

allgoodlife 7년 전 0

코드는 아래와 같고 예제 test case에 대한 결과는 알맞게 나오는 걸 확인하였습니다.

첫번째 시도에서 일일이 모든 석순과 종유석에 대하여 counting을 해주었고 시간초과가 나서

이미 질문하신분들의 시간초과에 대한 힌트를 참고하여 풀고자 했습니다.

lower_bound, upper_bound를 가지고 해결하려고 아래와 같이

짰습니다만 여전히 시간초과가 나오는데 어느부분에서 시간을 줄여줄 수 있을까요~

고수님들의 조언부탁드립니다.

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

int main(void){
	int width, height;
	cin >> width >> height;
	//석순
	vector<int> bottom(width/2);
	//종유석
	vector<int> up(width/2);
	//카운팅
	vector<int> count(height);
	for (int i = 0; i < width/2; i++)
	{
		cin >> bottom[i] >> up[i];
	}
	sort(up.begin(), up.end());
	sort(bottom.begin(), bottom.end());

	vector<int>::iterator l, u;
	//석순counting
	for (int i = 0; i < height; i++)
	{
		l = lower_bound(bottom.begin(), bottom.end(), i + 1);
		u = upper_bound(bottom.begin(), bottom.end(), i + 1);
		if (l != u){
			for (int j = 0; j < i+1; j++)
			{
				count[j] += u - l;
			}
		}
	}

	//종유석counting
	for (int i = 0; i < height; i++)
	{
		l = lower_bound(up.begin(), up.end(), i + 1);
		u = upper_bound(up.begin(), up.end(), i + 1);
		if (l != u){
			for (int j = 0; j < i + 1; j++)
			{
				count[height - j - 1] += u - l;
			}
		}
	}

	int result, num_result = 0;
	//각 높이에 대한 count를 정렬
	sort(count.begin(), count.end());

	//최솟값이 result
	result = count[0];

	//최솟값이 몇 개인지 구하는 부분
	for (int i = 0; i < count.size(); i++)
	{
		if (count[i] == result){
			num_result++;
		}
		else{
			break;
		}
	}

	cout << result << " " << num_result << endl;

	return 0;
}

dlwodnsdl 7년 전 0

구간마다 일일히 닿는 종유석의 개수를 구하기 보다는 위에서 부터 n번째 구간에서 부딪히는 종유석의 수는 위에서부터 n+1번째 구간에서 부딪히는 종유석의 수+길이가 n인 종유석의 수인 것을 이용하면 O(n)의 시간만에 해결이 가능하니다.

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

문제

문제

출처

ICPC

시간복잡도 및 시간초과에 대하여 도움 요청드립니다.

allgoodlife 7년 전 0

dlwodnsdl 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말