백준 2467 c++ "용액" -PlusUltraCode-

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

 

[필자 사고]

정렬되어 있다. 이 키워드를 통해 이 문제는 이분탐색 아니면 투포인터이지 않을까?? 와 같은 사고를 했다. 

문제를 읽어보니 부르스트 알고리즘을 적용하면 시간내에 못 풀게 되어 있다.

역시나 투포인터 알고리즘을 이용해야 된느 문제이다.

O(nlogn) 시간복잡도로 충분히 시간 내에 풀 수 있다.

 

필자가 실수 했던 부분은 초기화 부분에 있었다. 

1. 먼저 long 으로 해야된다.

2. arr[left]+ arr[right] 등의 숫자들을 미리 담아나야된다.

 

이 부분만 신경쓰면 쉽게 해결할 수 있따.

[코드 해설]

 

• Input 함수
  • N개의 정수를 입력받는다.
  • 입력된 정수들을 저장할 arr 벡터를 초기화하고, 순서대로 값을 저장한다.
• Two_Pointer 함수
  • 두 포인터(left와 right)를 사용하여 배열의 양 끝에서 시작한다.
  • 각 반복마다 arr[left]와 arr[right]의 합을 계산하고, 절댓값이 최소가 되는 경우를 찾는다.
  • 만약 현재 합(nowSum)이 음수라면, left를 오른쪽으로 이동하여 값을 증가시킨다.
  • 반대로 nowSum이 양수라면, right를 왼쪽으로 이동하여 값을 감소시킨다.
  • 이 과정을 통해 두 값(leftValue, rightValue)의 합이 0에 가장 가까운 조합을 찾는다.
• GameStart 함수
  • Two_Pointer 함수를 호출하여 최소 절댓값 합을 구한다.
  • 구한 결과(leftValue와 rightValue)를 출력한다.
• main 함수
  • Input 함수를 호출하여 데이터를 입력받는다.
  • GameStart 함수로 로직을 실행하고 결과를 출력한다.

 

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<long> arr;
long resultSum = 987654321;
long leftValue=0, rightValue=0;


void Input() {
	cin >> N;
	arr.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
}

void Two_Pointer() {
	int left = 0;
	int right = N - 1;
	
	leftValue = arr[left];
	rightValue = arr[right];
	resultSum = abs(arr[left] + arr[right]);

	while (left < right) {
		long nowSum = arr[left] + arr[right];
		if (resultSum > abs(nowSum)) {
			resultSum = abs(nowSum);
			leftValue = arr[left];
			rightValue = arr[right];
		}

		if (nowSum < 0)left++;
		else right--;
		//음수면 왼쪽을 오른쪽으로
		//양수면 right 을 감소
	}
}

void GameStart() {
	Two_Pointer();
	cout << leftValue << " " << rightValue;
}

int main(void) {
	Input();
	GameStart();
}