[C++] 2467번 용액 - 두 포인터

#include <iostream>
#include <algorithm>

#define LOOP(i, N) for(int i=1; i<=N; i++)
#define MAX_N 100001
#define INF 2000000001

using namespace std;
typedef long long int lld;

int N;  //용액의 수 N
lld minv;
int minid1, minid2;  //최솟값과 그 인덱스
lld sum;  //용액의 합
lld num[MAX_N];  //용액의 특성값

void input()
{
    cin >> N;
    LOOP(i, N) cin >> num[i];
}

void f(int l, int r)  //두 포인터
{
    if(l==r)  //모두 탐색했을 경우 종료
        return;
    
    sum = num[l]+num[r];
    
    if(abs(sum) < abs(minv)) {  //특성값이 0에 더 가까우면 갱신
        minv=sum;
        minid1=l, minid2=r;
    }
    if(sum>0)
        f(l, r-1);
    else if(sum<0)
        f(l+1, r);
    else
        return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    input();
    
    sort(num+1, num+N);  //오른차순으로 정렬하기
    
    minv = INF;
    f(1, N);
    
    cout << num[minid1] << ' ' << num[minid2];
    
    return 0;
}

간단한 투 포인터 문제다. 왼쪽 맨 끝과 오른쪽 맨 끝에서 합을 더하면서 0보다 크면 왼쪽을 한 칸 오른쪽으로 밀고, 0보다 작으면 오른쪽을 왼쪽으로 한 칸 밀어서 합을 0으로 만드는 과정이다.

 

나는 함수로 해서 풀었는데 while:(l<r)로 배열로도 풀 수 있는 것 같다. 다른 사람이 그렇게 풀어놔서 밑에 링크가 있다.

 

<시행착오>

1. 합의 최댓값이 많이 크다. 987654321이 아닌 1,000,000,000의 두 배 크기이니 INF를 잘 잡아야 한다.

 

 

<배열(풀어야 볼 수 있습니다)>

https://www.acmicpc.net/source/22671315

로그인

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.