[정올 2788] 도약

http://jungol.co.kr/bbs/board.php?bo_table=pbank&code=2788&sca=99 

JUNGOL

// 시간복잡도 O(N^2logN)
// 세번째 좌표에 대해서 logN으로 탐색하는 방법
#include <cstdio>
#include <iostream>
#include <algorithm>
int N;
int leaf[1000 + 10];
int ans;


void input(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &leaf[i]);
	}
}

int BS_lower(int target)	// target 값보다 크거나 같은 값 중 가장 작은 값 찾기
{
	int s = 0;
	int e = N - 1;
	int pivot = 0;
	int lb = -1;

	while (s <= e) {
		pivot = (s + e) / 2;

		if (leaf[pivot] >= target) {
			lb = pivot;
			e = pivot - 1;
		}
		else s = pivot + 1;
	}
	return lb;
}

int BS_upper(int target)	// target 값보다 작거나 같은 값 중 가장 큰 값 찾기
{
	int s = 0;
	int e = N - 1;
	int pivot = 0;
	int ub = -1;

	while (s <= e) {
		pivot = (s + e) / 2;

		if (leaf[pivot] <= target) {
			ub = pivot;
			s = pivot + 1;
		}
		else e = pivot - 1;
	}
	return ub;
}


void jump(void)
{
	std::sort(leaf, leaf + N);	// 연잎 오름차순 정렬

	for (int i = 0; i < N - 2; i++) {
		for (int j = i + 1; j < N - 1; j++) {
			int len = leaf[j] - leaf[i];
			int lb = BS_lower(leaf[j] + len);
			
			if (lb < 0) break;
			else {
				int ub = BS_upper(leaf[j] + (len * 2));
				ans += ub - lb + 1;
			}
		}
	}

}


int main()
{
	input();
	jump();
	printf("%d", ans);
	return 0;
}

// 시간복잡도 O(N^3)
// for문 3개를 돌려 구현하는 방법
#include <cstdio>
#include <iostream>
#include <algorithm>
int N;
int leaf[1000 + 10];
int cnt;

void input(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &leaf[i]);
	}
}


bool compare(int p, int q)
{
	return p < q;	
}


void jump(void)
{
	std::sort(leaf, leaf + N, compare);	// 연잎 오름차순 정렬

	for (int i = 0; i < N - 2; i++) {
		int start = leaf[i];
		for (int j = i + 1; j < N - 1; j++) {
			int mid = leaf[j];
			int len1 = mid - start;
			for (int k = j + 1; k < N; k++) {
				int end = leaf[k];
				int len2 = end - mid;
				if (len2 < len1) continue;	// 두 조건문의 속성이 다르므로 
				if (len2 > 2 * len1) break;	//분리해서 써주면 더 빨라진다. 
				cnt++;
			}
		}
	}
}

int main()
{
	input();
	jump();
	printf("%d", cnt);
	return 0;
}

깨구락지의 연잎도약.... 알고리즘 깨구락지인 나도 도약할 수 있겠즈ㅣ...? 개굴개굴..

 

이 문제는 연잎의 수가 최대 1000이라서 삼중 for문으로 구현해도 타임아웃이 나지 않는다. (최대 1,000,000,000번 돌아감) 따라서 두 번째 방법으로 풀어도 되긴 되지만, 출제자의 의도가 아닐 뿐더러 N값이 커지면 바로 타임아웃이 뜰 것이기 때문에 첫번째 방법을 권장한다. 

 

 

배열의 범위가 크고, 선형적인 탐색을 하는 경우이기 때문에 "이분탐색"을 떠올려야 한다. 

// jump( ) 함수

첫번째랑 두번째 연잎까지는 어쩔 수 없이 for문을 돌려 탐색해줘야 한다.

대신 (1, 3, x) 이런식으로 원소가 두 개 정해지면, 가장 마지막에 도약할 연잎은 이분탐색으로 구할 수 있다. 

문제의 조건에서 개구리는 "이전의 뛴 거리 이상 뛰지만, 그 2배보다 멀리 뛰지는 않는다"고 하였다. 따라서 개구리가 뛸 수 있는 연잎의 "하한선(lower bound; lb)"을 구할 때는 타겟값을 (두번째 원소 + 첫 번째 원소와 두 번째 원소 사이의 거리) 로 두었고, "상한선(upper bound; ub)"을 구할 때는 타겟값을 (두 번째 원소 + 2 * (첫 번째 원소와 두 번째 원소 사이의 거리))로 두고 탐색하였다, 

마지막으로 하한값의 인덱스와 상한값의 인덱스 사이에 있는 값들은 모두 개구리가 도약할 수 있는 마지막 원소가 된다. 따라서 ans += ub - lb + 1를 통해 경우의 수를 누적한다. 

 

 

// BS_lower( ) 함수

하한선을 구하는 함수이다. 

즉, "배열의 원소 중 함수의 인자로 보낸 타겟값보다 크거나 같은 값 중 가장 작은 것"을 구해야 한다.  

lb = -1로 둔 이유는 적합한 원소가 없는 경우 음수 값을 리턴하여 예외처리해 주기 위함이다. 

조건 (s <= e)를 만족하는 동안 무한루프가 돌며, 만약 leaf[pivot] >= target 이면 배열의 원소 중 타겟보다 큰 값을 찾은 것 이므로 pivot을 정답의 후보(lb)로 넣는다. 그리고 이와 같은 조건을 만족하는 배열의 원소 중 가장 작은 수를 찾기 위해 e = pivot - 1로 갱신하여 더 작은 값들을 탐색한다. 

만약 leaf[pivot] < target 이면 배열의 원소가 타겟값보다 작은 경우 이므로, s = pivot + 1으로 시작점을 갱신하여, 더 큰 배열의 원소를 탐색한다. 

 

 

// BS_upper ( ) 함수

상한선을 구하는 함수이다. 

로직은 BS_lower 함수와 비슷하지만, 이 함수는 "배열의 원소 중 함수의 인자로 보낸 타겟값보다 작거나 같은 값 중 가장 큰 것"을 구한다. 

위와 동일하게 조건 (s <= e)를 만족하는 동안 무한루프가 돌며, 만약 leaf[pivot] <= target이면 배열의 원소 중 타겟보다 작은 값을 찾은 것이므로 pivot을 정답의 후보(ub)로 넣는다. 그리고 이와 같은 조건을 만족하는 배열의 원소 중 가장 큰 수를 찾기 위해 s = pivot + 1로 갱신하여 더 큰 값들을 탐색한다. 

만약 leaf[pivot] > target이면 배열의 원소가 타겟값보다 큰 경우 이므로, e = pivot - 1으로 끝점을 갱신하여 더 작은 배열의 원소를 탐색한다.