알고리즘/백준

[백준 2473] 세 용액 C++

겜도리도리 2023. 2. 20. 20:28
반응형

문제

백준 2473 세 용액 C++

 

2473번: 세 용액

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상

www.acmicpc.net

풀이

용액문제 (https://gamedoridori.tistory.com/238)의 심화형이다.

오름차순으로 용액이 정렬되어있지 않으므로 먼저 정렬을 해준다.

그리고 각각의 용액에 대해, 그 용액과 합의 절댓값이 최소가 되는 두 용액을 두 포인터로 찾아준다.

 

여담으로 용액과 두 용액 문제는 입력값이 -10억~10억이라 int 자료형으로도 문제가 없었지만, 세 용액 문제는 int 자료형을 사용할 시에 abs 함수 사용시에 문제점이 있었다. 다른 해결책도 있겠지만, 편의상 long long 자료형으로 바꿔주었다.

소스 코드

슷ㅅㅅ
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int N;
    cin >> N;
    vector<long long> input;
    input.reserve(N);
         
    for (int i = 0; i < N; i++)
    {
        long long num = 0;
        cin >> num;
        input.push_back(num);
    }
 
    sort(input.begin(), input.end());
 
    long long result1 = input[0];
    long long result2 = input[1];
    long long result3 = input[N - 1];
    long long minAdd = abs(result1 + result2 + result3);
 
    for (int idx = 0; idx < N; idx++)
    {
        int start = 0;
        int end = N - 1;
 
        while (start < end)
        {
    ㅅ        if (start == idx)
            {
                start++;
                continue;
            }
                
            else if (end == idx)
            {
                end--;
                continue;
            }
 
            long long add = input[start] + input[end+ input[idx];
            long long absAdd = std::abs(add);
            if (absAdd < minAdd)
            {
                minAdd = absAdd;
                result1 = input[start];
                result2 = input[end];
                result3 = input[idx];
            }
 
            if (add > 0)
            {
                end--;
            }
            else
            {
                start++;
            }
        }
    }
 
 
    vector<long long> result;
    result.push_back(result1);
    result.push_back(result2);
    result.push_back(result3);
 
    sort(result.begin(), result.end());
 
    for (auto e : result)
    {
        cout << e << ' ';
    }
 
    return 0;
}
cs
반응형

'알고리즘 > 백준' 카테고리의 다른 글

[백준 5972] 택배 배송 C++  (1) 2023.03.03
[백준 10025] 게으른 백곰 C++  (0) 2023.02.23
[백준 2467] 용액 C++  (0) 2023.02.19
[백준 1937] 욕심쟁이 판다 C++  (1) 2023.02.11
[백준 17299] 오등큰수 C++  (0) 2023.01.12