[백준 2467, 2470] 용액, 두 용액

https://www.acmicpc.net/problem/2467

2467번: 용액

https://www.acmicpc.net/problem/2470

2470번: 두 용액

#include <cstdio>
#include <algorithm>
#include <cstdlib>
int N;
int arr[100000 + 2];
int min = 0x7fffffff;
int idx1;
int idx2;

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


void get_max()
{
	int s = 0;
	int e = N - 1;

	while (1) {
		if (s >= e) return;

		int tmp = arr[s] + arr[e];
		if (abs(min) > abs(tmp)) {
			min = tmp;
			idx1 = s;
			idx2 = e;
			if (tmp == 0) return;	// 합이 0이면 더이상 탐색할 필요 없음 
		}

		if (tmp < 0) s++;
		else e--;
	}
}


int main()
{
	input();
	get_max();
	printf("%d %d\n", arr[idx1], arr[idx2]);
	return 0;
}

어차피 똑같은 문제인데 정렬된 채로 입력값이 들어오느냐, 아니냐의 차이이므로 sort가 포함된 코드 하나만 올리겠다. 

 

 

// get_max( ) 함수 

투 포인터 문제이다.

s 포인터는 시작인덱스, e 포인터는 배열의 마지막 인덱스를 가리키도록 초기 설정해준다. 

그리고 무한루프를 도는데, 만약 s >= e 이면, 즉 두 포인터가 같거나 엇갈리는 경우 루프를 중단한다. 모든 경우를 다 탐색한 후 이기 때문이다. 

임시변수 tmp에는 s 포인터가 가리키는 값과 e 포인터가 가리키는 값을 더해준다. 즉, 두 용액을 합성해준다. 만약 해당 값의 절댓값(즉 tmp와 0 사이의 거리)이  min의 절댓값(즉 min과 0사이의 거리) 보다 작으면 min을 tmp로 갱신하고, 두 인덱스를 저장한다. 

 

만약 tmp == 0 이면  더이상 탐색할 필요 없이 루프를 중단한다. (특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력하면 되기 때문)

만약 tmp < 0 이면 끝 인덱스(e)가 배열의 마지막 원소부터 탐색을 시작하기 때문에, 시작 인덱스(s) 를 기준으로 두 용액의 합을 양수로 만들 더 큰 값은 없다. 따라서 s의 위치를 한 칸 전진(++)한다. 

만약 tmp > 0 이면 시작 인덱스를 기준으로 큰 값만 탐색한 경우이므로, e의 위치를 한 칸 후진(--)하여 더 작은 값과 합성해본다.