용액

작성일 | In

[백준] 2467번 - 용액

문제 링크

KOI 2010 초등부 문제.
합이 0에 가장 가까운 두 용액을 고르는 문제이다.
입력으로 주어진 용액 배열의 첫 인덱스와 마지막 인덱스를 시작으로 점점 중심으로 조여가며 greedy하게 풀면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

vector<int> src;
int mixed=2000000000; // 주어진 용액은 전부 서로 다르므로 두 용액의 합의 절댓값이 20억을 넘을 수 없다. 
int as, ae;

int main(void) {
    int n;
    scanf("%d", &n);

    src.resize(n);
    for(int i=0; i<n; ++i)
        scanf("%d", &src[i]);

    int s=0, e=n-1;
    while(s < e) {
        int curMixed = src[s] + src[e];
        if(abs(curMixed) < mixed) {
            as = s; ae = e;
            mixed = abs(curMixed);
        }
        if(curMixed < 0) ++s;
        else if(curMixed > 0) --e;
        else break;
    }
    printf("%d %d", src[as], src[ae]);
}
0%