[백준 2473번] 세 용액

BOJ 2473번

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

백준 2473번 C++ 소스

브루트포스로 i, j, k 변수 선언하고 3중 for문으로 풀려고 했었으나, 그렇게 되면 N^3 이라 

시간초과가 날 수 밖에 없다.  

https://en.wikipedia.org/wiki/3SUM 에 힌트가 있었다. 

fix라는 변수를 이용해서 하나를 딱 정한다음에  start와 end를 이용해서 점점 조여오는 방법이다. 

i) 3개의 수 합이 0보다 클 경우  0에 가깝기 만들기 위해 end를 하나 줄여서  작은수를 대입시킨다. 

ii) 3개의 수 합이 0보다 작을 경우  0에 가깝기 만들기 위해 start를 하나 늘려서  큰 수를 대입시킨다. 

iii)   i, ii 의 경우에 모두 해당하지 않는 경우는 0이므로 i=N으로 두어 for (i = 0; i < N - 2; i++) 반복문을 탈출하게 하고  while(true) 반복문도 역시 빠져나온다. 

입력받은 배열 arr를 이미 오름차순으로 정렬해두었기 때문에  위 3가지 방법이 쉽게 가능하게 된 것이다.

start와 end를 조절하면서 total값과  현재의 3개 수 절대값 합을 비교해본다.

만약 현재의 3개 수 절대값 합이 더 작으면 해당하는 그 index를 기억하기 위해

 a, b, c변수에 저장하고 아니라면 그냥 skip한다.   

start와  end값이 같아지면 while문을 빠져나오고 fix를 하나 올리고 다시 과정을 반복하는 코드이다.

사용했던 테스트 케이스

7

-2 -3 -24 -6 98 100 61

6

-35 1 2 3 35 1000

6

-1 -2 -3 99 -99 1000

5

-1 -2 -3 99 -99

5

-2 6 -97 -6 98

5

1 2 3 4 5

5

-1 -3 -7 -9 1000

5

-9 -7 -3 7 1000

6

-5 1 2 3 4 999

6

-5 1 2 3 7 999

소스코드

#include "pch.h"
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;

int main(void)
{
	long long arr[5001], total = 9223372036854775807;
	int N;
	int i;
	int fix, start, end;
	int a, b, c;

	cin >> N;

	for (i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	sort(arr, arr + N);

	for (i = 0; i < N - 2; i++)
	{
		fix = i;
		start = fix + 1;
		end = N - 1;
		
		while (true)
		{
			if (start == end) break;
			
			if (abs(arr[fix] + arr[start] + arr[end]) < total)
			{
				a = i;
				b = start;
				c = end;
			}

			total = min(total, abs(arr[fix] + arr[start] + arr[end]));

			if (arr[fix] + arr[start] + arr[end] > 0)
			{
				end--;
			}
			else if (arr[fix] + arr[start] + arr[end] < 0)
			{
				start++;
			}
			else
			{
				i = N;
				break;
			}
		}
	}

	cout << arr[a] << ' ' << arr[b] << ' ' << arr[c] << endl;

	return 0;
}

개발환경 및  컴파일 기준은 visual studio community 2017