코딩테스트 챌린지

2025/02/08 백준 2473 세 용액

달팽이포뇨 2025. 2. 8. 15:42

난이도: G3

알고리즘: 이분탐색

 

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

 

1. 문제 탐색

 

제한 시간: 1초, 메모리 제한: 256MB

 

N이 최대 5000 이므로 5000*연산<10^9이려면 대략 연산은 2*10^6 이하여야한다.

이분탐색으로 풀어서 연산 횟수를 줄이자.

 

2. 코드 설계하기

이분탐색을 하기 위해 용액의 특성값을 먼저 오름차순으로 정렬한다.

배열을 하나씩 돌면서 v[i]를 기준 용액으로 정하고 v[i+1]~v[n-1] 용액 중에 2개를 고르는 방식으로 진행한다.

특성값의 합이 0에 가까워야한다는 조건이 있기 때문에 특성값의 총합 뿐만 아니라 절대값으로 판단하는 과정도 들어가야한다.

 

3. 시도회차별 수정 사항

 

거의 모든 변수를 long long으로 해놓고 코드를 작성해야한다.

int변수로 설정하고 이후에 long long으로 자료형 변환을 하려고 하면, 실수가 발생하여 연산 과정에서 자동으로 int로 변환되는 경우가 생길 수 있다. 

 

4. 정답코드

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

using namespace std;

int main()
{
    int n;
    long long ans1, ans2, ans3;
    long long abs_sum = 6000000000;
        
    //입력
    cin>>n;

    vector<long long> v(n, 0);
    
    for(int i=0; i<n; i++)
    {
        cin>>v[i];
    }

    //정렬
    sort(v.begin(), v.end());

    //탐색
    for(int i=0; i<n-2; i++)
    {
        int left = i+1;
        int right = n-1;

        while(left<right)
        {
            long long mix = v[i]+v[left]+v[right];
            
            if(abs(mix)<abs_sum) //합이 0에 가까울경우 abs_sum 갱신
            { 
                ans2 = v[left];
                ans3 = v[right];
                ans1 = v[i];

                abs_sum = abs(mix);
            }

            if(v[i]+v[left]+v[right]>0)
            {
                right--;
            }
            else{
                left++;
            }
        }
    }

    cout<<ans1<<' '<<ans2<<' '<<ans3;

}