[ C++ 백준 2473 ] 세 용액

이 블로그 글은 문제에 대한 해설이 아닌 글쓴이가 이 문제를 푼 과정을 설명하는 글입니다.

문제에 대한 해설을 보길 원한다면 다른 글을 권장합니다.

---

골드 이상 난이도 백준 문제를 풀 때는 알고리즘 분류를 보고 푸는 편이다.

정렬, 이분 탐색, 두 포인터를 사용해서 푸는 거라는 힌트를 받을 수 있다.

 

---

문제를 간단하게 요약하자면

여러 용액이 입력되고, 서로 다른 3개의 용액을 선택해서 합했을 때

0에 가장 가까운 용액을 만들어내는 세 용액을 찾는 프로그램을 작성하면 된다.

 

그렇다면 어떻게 풀 수 있는가?

알고리즘 분류를 보면 정렬, 이분 탐색, 두 포인터를 사용하라고 나와있다.

---

어떻게 풀어야 할까?

일단은 용액 3개를 선택해야 된다는 게 문제였다.

용액 2개라면 간단하게 두 포인터를 이용해서 풀 수 있었는데

용액이 3개라서 두 포인터를 어떻게 사용할지 감이 잘 안 잡혔다.

 

이분 탐색은 어디에 사용되는거지

라는 고민을 하다가 그냥 포인터 갯수를 세 개로 늘리면 되지 않을까 하고 접근하였다.

 

[ 코드 ]

 

#include <iostream>
#include <algorithm>

using namespace std;

int solutions[5001];
int answerIdxs[3];	// 정답 인덱스들을 저장하는 값
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(); 
	cout.tie();

	int N;		// 전체 용액의 수
	cin >> N;

	for (int i = 0; i < N; ++i)	// 용액 입력 받기
		cin >> solutions[i];

	//정렬하기
	sort(solutions, solutions + N);

	long int ansVal = 3000000000;
	int p1 = 0, p2 = 1, p3 = 2;
	while (true)
	{
		long int tempVal = abs(solutions[p1] + solutions[p2] + solutions[p3]);
		if (tempVal < ansVal)
		{
			answerIdxs[0] = p1;
			answerIdxs[1] = p2;
			answerIdxs[2] = p3;
			ansVal = tempVal;
		}
	}
}

근데 p1, p2, p3를 어떻게 더해야 탐색이 잘 될지 감이 안 잡혔다.

 

이분 탐색을 사용해서 해결해보자라는 생각을 했다.

p1, p3는 잘 될 것 같았지만 p2를 어떻게 할지 생각이 나지 않았는데

그래서 그냥 p2를 전부 탐색해보기로 했다.

 

그렇게 이런 저런 고생을 하다가 해결한 코드다.

 

[ 정답 코드 ]

#include <iostream>
#include <algorithm>

using namespace std;

long long solutions[5001];
int answerValues[3];					// 정답 값들을 저장하는 값
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(); 
	cout.tie();

	int N;								// 전체 용액의 수
	cin >> N;

	for (int i = 0; i < N; ++i)			// 용액 입력 받기
		cin >> solutions[i];
	sort(solutions, solutions + N);		// 정렬하기

	long long ansVal = 3000000000;
	int p1 = 0, p2 = 1, p3 = 2;
	for (int p1 = 0; p1 < N - 2; ++p1)	// p2 = i + 1, p3 = N - 1부터 시작
	{
		p2 = p1 + 1;
		p3 = N - 1;
		while (p2 < p3)
		{
			long long tempVal = (solutions[p1] + solutions[p2] + solutions[p3]);
			long long absTempVal = abs(tempVal);
			if (absTempVal < ansVal)
			{
				answerValues[0] = solutions[p1];
				answerValues[1] = solutions[p2];
				answerValues[2] = solutions[p3];
				ansVal = absTempVal;
			}

			if (tempVal < 0) p2++;
			else p3--;
		}
	}
	
	for (int i = 0; i < 3; ++i)
		cout << answerValues[i] << ' ';
}

원래는 솔루션 배열이 int 였는데 tempVal을 구할 때 오버플로우가 나는 것 같아서 long long으로 바꿨다.