글 읽기 - 이번 코더스하이 예선 I번 문제 시간초과ㅠㅠ

dygks232 7년 전 0

제가 짠 코드는 아래와 같습니다. 접근은 맞게 한 것 같은데 시간초과를 여기서 도저히 못줄이겠네요 ㅠㅠ

대회 당시 별생각 없이 짜다보니 대학자료구조시간에 배우는 희소행렬 개념을 사용하게 된 것 같은데, 접근법이 잘못된걸까요? 아니면 여기서 더 효율적으로 짜는 방법이 있는 걸까요?

대회당시에 이 문제 성공한팀이 1팀도 없던데ㅠㅠ 고수님들 조언좀 부탁드립니다...

#include<iostream>
#include<cmath>
using namespace std;

// 1번 연산으로 입력받은 x좌표, y좌표, 거리r 이 각 열에 차례대로 들어간다.
// 1번 연산을 수행할 때마다 cache의 다음 행에 기록된다.
int cache[200000][3] = { 0, };


// 벌집좌표계에서 (x1,y1)과 (x2,y2) 사이의 거리가 r 이하인지 검사하는 함수
bool f(int x1, int y1, int x2, int y2, int r)
{
	int dist;
	int a = x2 - x1;
	int b = y2 - y1;
	int aa = abs(a);
	int ab = abs(b);


	if (a == 0) dist = ab;
	else if (b == 0) dist = aa;
	else if (a*b < 0) dist = aa + ab;
	else
	{
		dist = aa > ab ? aa : ab;
	}
	if (dist <= r) return true;
	else return false;
}


int main()
{
	ios::sync_with_stdio(false);
	int size, cal, i;
	// 벌집의 사이즈, 연산의 수를 차례로 입력받음.
	cin >> size >> cal;

	int count = 0; // 지금까지 입력받은 1번 연산의 수
	int type, x, y;

	while (cal--)
	{
		cin >> type; // 1번연산인지 2번연산인지?
		if (type == 1)
		{
			// cache에 정보 저장 후 count 증가
			cin >> cache[count][0] >> cache[count][1] >> cache[count][2];
			count++;
		}
		else{
			cin >> x >> y;
			int result = 0; // 입력받은 (x,y)좌표에 어떤 값이 있는지를 나타낼 변수
			for (i = 0; i < count; i++)
			{
				if (f(x, y, cache[i][0], cache[i][1], cache[i][2])) result++;
			}
			cout << result << endl;
		}
	}

	//system("pause");
	return 0;
}

ntopia 7년 전 0

이렇게 하면 시간복잡도가 대략 O(Q^2) 이라 시간초과 입니다.

2차원 펜윅트리를 쓰면 된다고 주워들었습니다.

자세한건 코더스하이 풀이가 나오면 그걸 참고하시는게... 좋겠네요...

dygks232 7년 전 0

오... 처음듣는 개념이네요... 공부해보겠습니다!! 감사합니다ㅎㅎ

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

문제

문제

출처

ICPC

이번 코더스하이 예선 I번 문제 시간초과ㅠㅠ

dygks232 7년 전 0

ntopia 7년 전 0

dygks232 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말