글 읽기 - 시간 초과 및 문제 질문 드립니다.

totok682 4년 전 0

사실 처음에 시도했던 방법은

도킹 돼있는지 판별하기위한 bool 형 배열을 선언해놓고

g_i 를 입력받아 거꾸로 반복문을 돌면서 해결하고자 했으나 시간초과가 떠서 인터넷을 검색해보았습니다.

두번째로 시도한 방법은

유니온-파인드 카테고리에 있기도하고 인터넷에서는 유니온 파인드 구조를 통해 해결하는 것으로 보여서

아래와 같이 코드를 짰는데 이 마저도 시간 초과가 발생합니다.

저는 시간 초과가 뜨는게 당연하다고 생각하는게 두번째 방법에서 find 함수의 반복횟수나 bool 형 배열을 두고 반복문을 두는 것이랑 같다고 생각합니다. 오히려 첫 번째 방법이 빠르다고 생각하는데요.

그래서 시간을 줄이기 위해,

세번째로 시도한 방법은

아래 코드와 같이 bool 형 배열과 이분 탐색 알고리즘을 사용한 방법이었는데,

이번엔 틀리다고 나오네요.. 어디가 잘못된건지 도와주실 수 있으실까요 ㅠㅠ

#include <iostream>

using namespace std;
const int max_num = 100000;
bool arr[max_num + 1];
int G, P;

bool binary_docking(int max, int low = 1)
{
	if (max < low)
		return false;
	if (!arr[max])
	{
		arr[max] = true;
		return true;
	}
	
	int middle = (max + low) / 2;

	if (!arr[middle])
		return binary_docking(max - 1, middle);
	else
		return binary_docking(middle - 1, low);
}


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int count = 0;
	cin >> G >> P;

	for (int i = 1; i <= P; i++)
	{
		int n;
		cin >> n;
		if (binary_docking(n))
			count++;
		else
			break;
	}

	cout << count;

	return 0;
}

herdson 4년 전 3

실제 풀이를 보면 질문자님이 언급하신 첫번째 방법과 두번째 방법 둘다 존재합니다.

첫번째는 Clever counting이라고 불리던데

http://mmhs.ca/ccc/2015/2015s3MatthewLee.txt

다음 링크를 참조하면 될 것 같습니다.

유니온 파인드로 해결하려고 하실 경우 Union by rank을 하지 않아야 시간초과가 뜨지 않습니다.
유니온 파인드 구조에 대한 근본적인 이해가 필요한 부분입니다.

세번째는 솔직히 이분탐색이 먹힐 수 있을 것 같지는 않습니다.

totok682 4년 전 0

herdson

union by rank 가 아닌 경로 압축을 통해 해결했지만

도움이 됐습니다 ^ㅡ^ 감사합니다

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

문제

문제

출처

ICPC

시간 초과 및 문제 질문 드립니다.

totok682 4년 전 0

herdson 4년 전 3

totok682 4년 전 0

herdson

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말