백준 - 2467 용액

 

해결과정 - 투포인터

왼쪽과 오른쪽을 비교해가며 두 값의 합이 가장 0에 가까운 값을 알아내는 문제라는 것을 파악하였고 한가지 왼쪽을 증가할지 오른쪽을 감소할지를 결정하는 일만 남았다.

 

결론은 두 값의 절대크기를 비교하여 절대크기가 큰 쪽의 값을 증가시키거나 감소시키는 것다

3가지 경우의 수가 있는데

1. 왼쪽수는 음수 오른쪽 수는 양수일경우 : 절대크기가 작은쪽을 이동하면 0에서 멀어진다

2. 둘다 음수 : 절대크기가 작은쪽을 이동하면 0에서 멀어진다

3. 둘다 양수 : 위와 같다

 

로 나올수 있는 모든 경우의 수에서 절대크기가 큰쪽의 값을 이동해야 된다는 결론이 나왔다

 

솔직히 감각적으로 알긴했는데 항상 알고리즘은 증명이 필요하다고 개인적으로 생각한다

 

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<queue>
#include<deque>
#include<unordered_set>
#include<unordered_map>
#include<cmath>

#define Fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;

typedef long long ll;

int main() {
	Fast;
	int n;
	cin >> n;

	vector<int> arr(n);
	int left = 0, right = n - 1;
	int left_index = 0, right_index = n - 1;
	
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int cur_max = 2000000000;

	while (left_index < right_index) {
		int left_value = arr[left_index];
		int right_value = arr[right_index];

		int diff = abs(left_value + right_value);

		if (diff == 0) {
			cout << left_value << " " << right_value;
			return 0;
		}

		if (diff < cur_max) {
			cur_max = diff;
			left = left_value;
			right = right_value;
		}

		if (abs(left_value) > abs(right_value)) {
			left_index++;
		}
		else {
			right_index--;
		}
	}

	cout << left << " " << right;
	return 0;
	
}

 

 

 

후기

일주일동안 알고리즘 단련을 했더니 간단한 골드문제는 10~15분이면 해결하는 것같아 단련의 성과가 있구나 싶었다. 이제 본업인 게임개발에 집중하고 알고리즘은 하루에 1~2문제씩만 꾸준히 풀어야겠다