[C++] 2470: 두 용액

골드 Ⅴ

 

#include <iostream>
#include <algorithm>
#define ABS(x) ((x<0)?(-x):(x))
using namespace std;

int sol[100001];

int main() {
	int N;
	scanf("%d", &N);

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

	sort(sol, sol + N);

	int start = 0;
	int end = N - 1;
	int start_ans = 0;
	int end_ans = N - 1;

	int sum = sol[0] + sol[N - 1];
	int sum_ans = sum;

	while (start < end) {
		if (ABS(sum) < ABS(sum_ans)) {
			sum_ans = sum;
			start_ans = start;
			end_ans = end;
			if (ABS(sum) == 0) break;
		}

		if (sum < 0) {
			sum -= sol[start];
			sum += sol[++start];
		}
		else if (sum > 0) {
			sum -= sol[end];
			sum += sol[--end];
		}
	}
	printf("%d %d", sol[start_ans], sol[end_ans]);
}

 

난 맨 처음에 이렇게 풀었는데,

 

아래처럼 하는게 더 직관적이고 디버깅 하기도 쉬울듯! 이해도 잘 되고

 

#include <iostream>
#include <algorithm>
#define ABS(x) ((x<0)?(-x):(x))
#define INF 2100000000
using namespace std;

int sol[100001];

int main() {
	int N;
	scanf("%d", &N);

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

	sort(sol, sol + N);

	int start = 0;
	int end = N - 1;
	int start_ans = 0;
	int end_ans = N - 1;

	int sum = 0;
	int sum_ans = INF;

	while (start < end) {
		sum = sol[start] + sol[end];

		if (ABS(sum) < ABS(sum_ans)) {
			sum_ans = sum;
			start_ans = start;
			end_ans = end;
			if (ABS(sum) == 0) break;
		}

		if (sum < 0) start++; 
		else if (sum > 0) end--; 
	}
	printf("%d %d", sol[start_ans], sol[end_ans]);
}

 

아무튼 그냥 투 포인터 문제가 아니라

양쪽에서 접근하는 투 포인터 문제였다! --> 투 포인터 문제 두번째 유형

 

그리구 start부터 end까지 다 더하는 문제가 아니라

딱 start값이랑 end값의 합만 보는 나름의 응용? 문제 -> 두번째 유형이라는 뜻 모를 때 쓴거라.. ㅋㅋ

 

그리구 왼쪽/오른쪽 에서 서서히 접근해 오는거는 딱 느껴지겠지만

정렬이 필요함! --> 3273문제에서 이유를 말했지만.. 두번째 유형에서는 sum과의 관계성이 없기 때문임