본문 바로가기

알고리즘/백준

[백준/C++] 알고리즘 2467번 - 용액

 

안녕하세요! 테크지니어입니다.

오늘은 백준 알고리즘 2467번 용액 문제를 풀어보도록 하겠습니다.

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

 

2467번: 용액

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -

www.acmicpc.net

 

[문제접근]

시간제한은 1초이고, N은  10만이하이기 때문에 N^2은 100억이 되어 완전탐색은 시간초과가 발생합니다.

1차원 배열에서 특정 두 개의 용액을 찾는 문제라는 점에서 투 포인터를 떠올릴 수 있고, 정렬된 순서로 주어졌다는 점에서 이분 탐색까지 떠올릴 수 있습니다.

 

[풀이전략]

(1) 투 포인터 풀이

1. 가장 자리부터 확인하기 위해 st = 0, en = n-1로 초기화한다.

2. 절대값이 가장 작은 합 특성값을 저장할 변수 minTot 을 큰 값으로 초기화한다.(용액MAX * 2 + 1, 넉넉히 1을 더함)

3. sum = arr[st]+arr[en]의 절댓값이 minTot의 절대 값보다 작으면 minTot에 대입하고, 두 용액을 저장한다.

4. sum이 0보다 크면 en을 한 칸 감소시키고, 0보다 작으면 st를 한 칸 증가시킨다. 0과 같으면 풀이를 종료한다.

5. st랑 en이 다를 때까지 while문을 이용하여 상황을 반복한다.

 

(2) 이분 탐색 풀이

1. 순차적으로 용액을 하나 선택한다. for문 이용

2. 그 용액의 특성값*(-1)을 lower_bound를 이용하여 찾는다. (lower_bound는 원하는 값과 같은 혹은 큰 것들 중 최소의 인덱스를 리턴, 만약 없으면 담능공간의 가장 끝 인덱스 + 1을 반환) 

3. 찾은 lowerIdx, lowerIdx-1, lowerIdx +1 을 확인하면서 최소 합 특성값을 가진 두 용액을 업데이트한다.

 

[코드]

(1) 투 포인터 풀이

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

using namespace std;

typedef  long long ll ;
int n ; 
ll MAX = 1'000'000'000;
ll minTot = 2*MAX + 1 ; // 가장 작은 합 특성값 저장 
vector<int> v(2) ;  // 가장 작은 합 특성값을 만들어내는 두 용액 저장. pair로 해도 됨.
ll arr[100'001];

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n ; 
    for(int i = 0 ; i < n ; i++) cin >> arr[i];
    int st = 0 ;
    int en = n-1;
    
    while(st < en ){
        int sum = arr[st]+ arr[en];
        if(abs(minTot) > abs(sum)) {minTot = sum ;
            v[0] = arr[st];
            v[1] = arr[en];
        }
        if(sum > 0) en--;
        else if(sum < 0) st++;
        else break;
    }
    cout << v[0]<<' '<< v[1] ; 
}

 

(2) 이분 탐색 풀이

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

using namespace std;

typedef  long long ll ;
int n ; 
ll MAX = 1'000'000'000;
ll minTot = 2*MAX + 1 ;
vector<int> v(2) ; 
ll arr[100'001];

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n ; 
    for(int i = 0 ; i < n ; i++) cin >> arr[i];

    
    for(int i = 0 ; i < n ; i++){
        int lowerIdx= lower_bound(arr,arr+n, -arr[i]) - arr ; 
        
        // lowerIndex의 왼쪽
        if(lowerIdx != 0 && lowerIdx-1 != i && abs(arr[lowerIdx-1] + arr[i]) < abs(minTot)) {
            minTot = arr[lowerIdx-1] + arr[i]; 
            v[0] = arr[i];
            v[1] = arr[lowerIdx-1] ;
        }

        // lowerIndex
        if(lowerIdx < n  && lowerIdx != i && abs(arr[lowerIdx] + arr[i]) < abs(minTot)) {
            minTot = arr[lowerIdx] + arr[i]; 
            v[0] = arr[i];
            v[1] = arr[lowerIdx] ;
        }

        // lowerIndex의 오른쪽
        if(lowerIdx < n-1 && lowerIdx+1 != i && abs(arr[lowerIdx+1] + arr[i]) < abs(minTot)) {
            minTot = arr[lowerIdx+1] + arr[i]; 
            v[0] = arr[i];
            v[1] = arr[lowerIdx+1] ;
        }
    }
    if(v[0] > v[1]) cout << v[1] <<' '<< v[0] ;
    else cout << v[0] << ' '<< v[1];
}

 

[배울 점]

- 아무 생각이 들지 않을 때는 코드부터 생각하지말고, 문제의 핵심 조건을 고민하면서 어떤 식으로 접근할 지 고민을 먼저 하기.

- 테케가 틀렸을 때, 이분 탐색과 투 포인터는 경계 지점을 잘 확인할 것.