백준 2473 세 용액 (C++)

안유태·2023년 12월 18일
0

알고리즘

목록 보기
206/239

2473번: 세 용액

투 포인터를 이용한 문제이다. 이 문제에서는 세가지 용액의 값을 구해야하므로 세가지의 위치를 구해야한다. 반복문을 돌면서 i를 기준으로 투 포인터를 이용해주었다. 먼저 입력받은 값을 오름차순으로 정렬을 해주고, i를 고정으로 두고 i + 1과 끝의 값을 기준으로 투 포인터를 시작하여 합의 절대값을 구해 비교하며 절대값이 가장 작은 세가지 인덱스를 구해 출력해주었다.
처음에는 처음과 끝 값을 고정으로 하고 가운데 값을 이동하며 찾는 방식으로 구현을 했었는데 어딘가 잘못됬는지 계속 틀렸습니다가 나왔었다. 아마도 투 포인터 안에서 반복문을 돌다보니 모든 값을 탐색하지 못했던 것 같다. 반복문 안에서 투 포인터를 돌도록 바꾸었더니 통과를 하였다. 생각보다 시간이 오래 걸린 문제였다. 투 포인터를 활용하는 방식에 대해 잘 알아두어야 겠다.



#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int N;
long long A[5000];

void solution() {
    sort(A, A + N);

    int a, b, c;
    long long sum = 3000000000;
    for (int i = 0; i < N - 2; i++) {
        int start = i + 1, end = N - 1;

        while (start < end) {
            long long tmp = A[i] + A[start] + A[end];

            if (sum > abs(tmp)) {
                a = i;
                b = start;
                c = end;
                sum = abs(tmp);
            }

            if (tmp < 0) start++;
            else end--;
        }
    }

    cout << A[a] << " " << A[b] << " " << A[c];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    solution();

    return 0;
}
profile
공부하는 개발자

0개의 댓글