10. 2788 : 도약

원본 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2048&sca=50&sfl=wr_subject&stx=%EB%8F%84%EC%95%BD&sop=and

JUNGOL | 도약 > 문제은행

문제 풀이 : 

3중 포문 풀이 : 

//도약(3중루프)
#include <stdio.h>
int N;
int arr[1001];
int sorted[1002];

void merge(int list[], int left, int mid, int right) {
	int i, j, k, l;
	i = left;
	j = mid + 1;
	k = left;

	/* 분할 정렬된 list의 합병 */
	while (i <= mid && j <= right) {
		if (list[i] <= list[j])
			sorted[k++] = list[i++];
		else
			sorted[k++] = list[j++];
	}

	// 남아 있는 값들을 일괄 복사
	if (i > mid) {
		for (l = j; l <= right; l++)
			sorted[k++] = list[l];
	}
	// 남아 있는 값들을 일괄 복사
	else {
		for (l = i; l <= mid; l++)
			sorted[k++] = list[l];
	}

	// 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
	for (l = left; l <= right; l++) {
		list[l] = sorted[l];
	}
}
// 합병 정렬
void merge_sort(int list[], int left, int right) {
	int mid;

	if (left < right) {
		mid = (left + right) / 2; // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
		merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
		merge_sort(list, mid + 1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
		merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
	}
}

int main(void) {
	int cnt = 0;
	int jump1, jump2;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	merge_sort(arr, 0, N - 1);                                                //오름차순으로 정렬 https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
	for (int start = 0; start < N - 2; start++) {                            //첫번째 점프 시작 위치
		for (int first = start + 1; first < N - 1; first++) {                  //첫번째 점프 도착 위치
			jump1 = arr[first] - arr[start];                                //첫번째 점프 거리
			for (int second = first + 1; second < N; second++) {               //두번째 점프 도착 위치
				//개구리는 이전 보다 많이 뛰지만 2배 이상을 뛰진 않는다.
				jump2 = arr[second] - arr[first];                           //두번째 점프 거리
				//첫번째 점프 거리 이상에서 첫번째 점프 거리 2배 이내인 경우를 카운트
				if (jump2 >= jump1 && jump2 <= jump1 * 2) cnt++;
				//2배를 초과 한 경우를 제외 시키기
				if (jump2 > jump1 * 2) break;
			}
		}
	}
	printf("%d", cnt);
	return 0;
}

2중 포문 + 이진탐색 풀이 :

//도약(3중루프)
#include <stdio.h>
int N;
int arr[1001];
int sorted[1002];

void merge(int list[], int left, int mid, int right) {
	int i, j, k, l;
	i = left;
	j = mid + 1;
	k = left;

	/* 분할 정렬된 list의 합병 */
	while (i <= mid && j <= right) {
		if (list[i] <= list[j])
			sorted[k++] = list[i++];
		else
			sorted[k++] = list[j++];
	}

	// 남아 있는 값들을 일괄 복사
	if (i > mid) {
		for (l = j; l <= right; l++)
			sorted[k++] = list[l];
	}
	// 남아 있는 값들을 일괄 복사
	else {
		for (l = i; l <= mid; l++)
			sorted[k++] = list[l];
	}

	// 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
	for (l = left; l <= right; l++) {
		list[l] = sorted[l];
	}
}
// 합병 정렬
void merge_sort(int list[], int left, int right) {
	int mid;

	if (left < right) {
		mid = (left + right) / 2; // 중간 위치를 계산하여 리스트를 균등 분할 -분할(Divide)
		merge_sort(list, left, mid); // 앞쪽 부분 리스트 정렬 -정복(Conquer)
		merge_sort(list, mid + 1, right); // 뒤쪽 부분 리스트 정렬 -정복(Conquer)
		merge(list, left, mid, right); // 정렬된 2개의 부분 배열을 합병하는 과정 -결합(Combine)
	}
}

int lower(int s, int e, int d)
{
	int m;
	int back_up = -1;
	while (s <= e)
	{
		m = (s + e) / 2;
		if (arr[m] >= d)
		{
			back_up = m;
			e = m - 1;    //있어도 끝까지 왼쪽에서 찾아봐야해 
		}
		else {
			s = m + 1;
		}
	}
	return back_up;
}
int upper(int s, int e, int d)
{
	int m;
	int back_up = -1;
	while (s <= e)
	{
		m = (s + e) / 2;

		if (arr[m] <= d)
		{
			back_up = m;
			s = m + 1;    //있어도 끝까지 오른쪽에서 찾아봐야해
		}
		else
		{
			e = m - 1;
		}
	}
	return back_up;
}

int main(void) {
	int cnt = 0;
	int jump1, jump2;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	merge_sort(arr, 0, N - 1);                                              //오름차순으로 정렬 https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
	//BS로 풀어보기
	int lo, up, s, e;
	for (int start = 0; start < N - 2; start++) {                            //첫번째 점프 시작 위치
		for (int first = start + 1; first < N - 1; first++) {                    //첫번째 점프 도착 위치
			jump1 = arr[first] - arr[start];
			s = jump1 + arr[first];
			e = jump1 * 2 + arr[first];
			lo = lower(first + 1, N - 1, s);
			if (lo != -1 && arr[lo] <= e) {
				up = upper(first + 1, N - 1, e);
				cnt += up - lo + 1;
			}
			//printf("start =%d , jump1 =%d, s=%d, e=%d, lo=%d, up=%d\n", arr[start], arr[first], s, e, lo, up);
		}
	}
	printf("%d\n", cnt);
	return 0;
}

: 3중 포문 풀이와 이진 탐색 풀이가 있는데 이진 탐색이 압도적으로 성능이 좋다.

이진탐색의 경우 2중 포문 안에 이진 탐색이 있는데 1중 포문에서 첫번째 점프 시작 위치를 돌아가며 시도하고 2중 포문에서 첫번째 점프가 도착하는 지점( = 두번째 점프의 시작 지점)을 정한 뒤 이진탐색으로 두번째 점프가 도착하는 지점을 탐색 하면 된다.