[백준 알고리즘] 2467번 - 용액 (투 포인터)

1. 문제 및 예시 실행 결과

 

 투 포인터를 활용하는 문제... 나름 재밌었다. 보통 이런 경우는 이분탐색 처럼 구현을 하게 되는데 그 과정은 어렵지 않지만 어떤 문제로 접근해야하는지 찾는 과정이 이분탐색 혹은 투 포인터 문제의 핵심이라는 생각이 든다.

 

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

2467번: 용액

---

---

2. 풀이과정

 

 문제를 잘게 나눠봤다.

 

1. 입력

2. 이분탐색 진행

 

 왼쪽과 오른쪽으로 부터 시작하여 두 값의 합이 0보다 크면 음수쪽이 강해져야하기에 왼쪽으로 작으면 오른쪽으로 이동하였다. 시간복잡도는 O(N)으로 판단하였다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<long long> solution;

int main(void) {
	
	
	int N;
	int right, left;
	int ans_right, ans_left;
	long long ans = 9876543210;

	cin >> N;

	for (int i = 0; i < N; i++) {
		long long buff;
		cin >> buff;
		solution.push_back(buff);
	}

	right = N - 1;
	left = 0;

	while (left < right) {

		long long tmp = solution[right] + solution[left];

		if (abs(ans) > abs(tmp)) {
			ans_left = left;
			ans_right = right;
			ans = tmp;
		}
		
		if (tmp == 0)
			break;

		if (tmp > 0) {
			right--;
		}
		else {
			left++;
		}
	}

	cout << solution[ans_left] << ' ' << solution[ans_right];

	return 0;

}