본문 바로가기
알고리즘

[백준 2467] 알고리즘 NCT???일차 : 용액

by SiO2whocode 2021. 8. 30.
반응형

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

 

2467번: 용액

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

www.acmicpc.net

C++ 투포인터

산성도가 오름차순으로 정렬된 배열에서 두 용액의 산성도를 합했을때 가장 0에 가까운 두 용액을 찾는 문제

2470번 문제와 아주 유사하지만 정렬된 배열이라는 점이 다르다.

 

접근방법

양 끝 점에서 시작하여

두 수의 합이 0보다 크면 현재 값보다 더 작아져야 하므로 end 점을 1감소시키고

두 수의 합이 0보다 작으면 현재 값보다 더 커져야 하므로 start점을 1증가시킨다.

 

소스코드

#include <iostream>
using namespace std;

int main(){
    //input & init
    int N;
    cin >> N;
    
    int arr[N];
    for(int i = 0 ; i < N ; i++){
        cin >> arr[i];
    }
    
    long long min;
    int s,e,as,ae;
    
    //process
    as = s = 0;
    ae = e = N-1;
    min = llabs(arr[s]+arr[e]);
        
    long long sum = min;
    while(s < e){
        sum = arr[s]+arr[e];
        if(min > llabs(sum)){
            min = llabs(sum);
            as = s;
            ae = e;
        }
        
        if(sum < 0)
            s++;
        else
            e--;
    }
    
    //output
    cout << arr[as] << " "<< arr[ae] << "\n";
    return 0;
}
반응형

댓글0