728x90

 0. [c++] 백준


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


 1. 풀이


1) 1번 풀이는 이전에 백준 2470 - 두 용액을 풀면서 활용했었던 방법을 동일하게 활용하기 위해서 만든 코드이다.


기본적으로 3개의 합의 최솟값을 구하는 방법은 N^3의 방법으로 풀 수 있는데, 이러한 방법을 사용하면 5000^3은 1억이 넘는 계산이 필요해지면서 시간초과가 발생하게 된다.


이를 해결하기 위한 방법으로 미리 2개의 수를 더한 이후, 나머지 한개를 더해주어서 결과를 구해내는 방법이었다.


어떻게 하여 마무리를 하였지만, 아무리 생각해도 이게 슬라이딩 윈도우라는 생각이 들지 않아서 구글링을 해보았다.




2) 구글링을 통해 https://jaimemin.tistory.com/679에 들어가보았는데, 내가 원하던 방식의 풀이를 볼 수 있었다.


사실 밑의 코드보다 이 코드가 더 좋으니 찾아보시길 ㅜㅜ



 2. 소스코드


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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
vector<long long> Acid;
vector<long long> Basic;
 
vector<pair<long long, pair<int, int> > > AcidSum;
vector<pair<long long, pair<int, int> > > BasicSum;
 
long long Solve[3];
 
bool cmp(long long a, long long b) {
    return abs(a) < abs(b);
}
 
bool cmp2(pair<long long, pair<int, int> > a, pair<long long, pair<int, int> > b) {
    return abs(a.first) < abs(b.first);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int T;
    long long temp;
    
 
    //입력을 받아오자.
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> temp;
        if (temp < 0)
            Basic.push_back(temp);
        else
            Acid.push_back(temp);
    }
    //가져온 입력을 정렬해준다.
    sort(Acid.begin(), Acid.end());
    sort(Basic.begin(), Basic.end(), cmp);
 
    long long SUM = 3000000000;
 
    if (Basic.size() >= 3) {
        SUM = Basic[0] + Basic[1] + Basic[2];
        SUM = abs(SUM);
        Solve[2] = Basic[0];
        Solve[1] = Basic[1];
        Solve[0] = Basic[2];
    }
 
    if (Acid.size() >= 3) {
        if (SUM > Acid[0] + Acid[1] + Acid[2]) {
            Solve[0] = Acid[0];
            Solve[1] = Acid[1];
            Solve[2] = Acid[2];
        }
    }
 
    //3가지를 모두 더하도록 함수를 만든다면, 5000*5000*5000으로 시간초과를 하게된다.
//따라서 2개를 더한 배열을 만든 이후, 나머지 하나를 더해주는 방식을 택한다면? 5000*5000 + x*5000으로 시간 내 해결 가능!
    if (Acid.size() >=2) {
    
        for (int i = 0; i < Acid.size() - 1; i++)
            for (int j = i + 1; j < Acid.size(); j++) {
                AcidSum.push_back({ Acid[i] + Acid[j], {i,j} });
            }
        for (int i = 0; i < Basic.size(); i++)
            AcidSum.push_back({ Basic[i], {i,-1} });
        sort(AcidSum.begin(), AcidSum.end(), cmp2);
        for (int i = 0; i < AcidSum.size() - 1; i++) {
            //인접한 두개의 부호가 다른 경우
            if (AcidSum[i].first * AcidSum[i + 1].first <= 0) {
                if (SUM > abs(AcidSum[i].first + AcidSum[i + 1].first)) {
                    SUM = abs(AcidSum[i].first + AcidSum[i + 1].first);
                    if (AcidSum[i].first < 0) {
                        Solve[0] = AcidSum[i].first;
                        Solve[1] = Acid[AcidSum[i + 1].second.first];
                        Solve[2] = Acid[AcidSum[i + 1].second.second];
                    }
                    else {
                        Solve[0] = AcidSum[i + 1].first;
                        Solve[1] = Acid[AcidSum[i].second.first];
                        Solve[2] = Acid[AcidSum[i].second.second];
                    }
                }
            }
        }
    }
    
 
 
 
    
 
    if (Basic.size() >= 2) {
        for (int i = 0; i < Basic.size() - 1; i++)
            for (int j = i + 1; j < Basic.size(); j++) {
                BasicSum.push_back({ Basic[i] + Basic[j], {j, i} });
            }
        for (int i = 0; i < Acid.size(); i++)
            BasicSum.push_back({ Acid[i], {i,-1} });
        sort(BasicSum.begin(), BasicSum.end(), cmp2);
        for (int i = 0; i < BasicSum.size() - 1; i++) {
            //인접한 두개의 부호가 다른 경우
            if (BasicSum[i].first * BasicSum[i + 1].first <= 0) {
                if (SUM > abs(BasicSum[i].first + BasicSum[i + 1].first)) {
                    SUM = abs(BasicSum[i].first + BasicSum[i + 1].first);
                    if (BasicSum[i].first < 0) {
                        Solve[2] = BasicSum[i + 1].first;
                        Solve[0] = Basic[BasicSum[i].second.first];
                        Solve[1] = Basic[BasicSum[i].second.second];
                    }
                    else {
                        Solve[2] = BasicSum[i].first;
                        Solve[0] = Basic[BasicSum[i + 1].second.first];
                        Solve[1] = Basic[BasicSum[i + 1].second.second];
                    }
                }
            }
        }
    }
    
    for (int i = 0; i < 3; i++) {
        cout << Solve[i] << " ";
    }
    return 0;
}
cs


 3. 참고




질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!


저작자표시

'<백준> > |c++| normal' 카테고리의 다른 글

[c++] 백준 1300 - K번째 수(이진 탐색)  (0) 2019.07.04
[c++] 백준 1654 - 랜선 자르기(이진 탐색)  (0) 2019.07.04
[c++] 백준 2312 - 수 복원하기(소인수분해, 소수, 에라토스테네스의 체)  (0) 2019.06.12
[c++] 백준 11729 - 하노이 탑 이동 순서(재귀 호출)  (0) 2019.06.12
[c++] 백준 1476 - 날짜 계산  (0) 2019.06.12

+ Recent posts

티스토리툴바