백준 1253번: 좋다 [C++]

작성일 | In
골드 IV 골드 IV

문제

좋다

풀이

$A$에 $0$이 없다고 생각해 봅시다. $A$에서 두 수를 골라 더한 뒤 집합에 넣고, $A[i]$가 집합에 포함되는지 검사하면 됩니다.

$A$에 $0$이 포함된 경우에 $A[i]$의 개수가 두 개 이상이라면 $A[i]$는 좋은 수가 됩니다.

예외적으로, $A[i] = 0$인 경우는 $A[i]$의 개수가 세 개 이상이어야 합니다.

코드

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
#include <bits/stdc++.h>
using namespace std;

int A[2020];
set<int> s;
bool zero = false;
map<int, int> cnt;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        cnt.emplace(A[i], 0);
        cnt[A[i]]++;

        if (A[i] == 0) {
            zero = true;
            continue;
        }

        for (int j = 0; j < i; j++) {
            if (A[j] == 0)
                continue;

            s.insert(A[i] + A[j]);
        }
    }

    int answer = 0;
    for (int i = 0; i < N; i++) {
        if (s.contains(A[i]))
            answer++;
        else if (zero and cnt[A[i]] > (1 + (A[i] == 0)))
            answer++;
    }

    cout << answer;
    
    return 0;
}

백준 1253번: 좋다 [C++]