[BOJ/Gold 4] 백준 1253 좋다(C++)

문제 링크

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

1253번: 좋다

 

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

 

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

 

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

 

예제 입력 1

10
1 2 3 4 5 6 7 8 9 10

예제 출력 1

8

 

 

알고리즘 분류

• 자료 구조

 

풀이

주어지는 수의 개수는 최대 2,000개이므로, 이중 for문으로 일일히 서로 다른 2개의 수를 더할 수 있다.

먼저 주어지는 특정한 수의 개수가 몇 개인지를 map을 활용하여 기록한다.

그리고 서로 다른 2개의 수 A, B를 더한 값이 주어진 N개의 수에 포함된 수인지를 확인하고 포함된 수라면 몇 개가 주어졌는지를 확인하여 새로운 변수 Count에 개수를 저장한다. 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 하였으므로, 이 값이 A, B인지를 파악하여 A, B라면 Count의 값을 1 감소시킨다.

Count의 값이 1 이상인 경우, A, B를 더하여 A, B가 아닌 다른 수로 나타낼 수 있다는 뜻이므로 set에 삽입한다.

set에 포함된 수 각각을 key라고 하였을 때, key가 몇 번 주어졌는지를 나타내는 value들의 합이 정답이 된다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <set>
#include <algorithm>
#define MAX 2001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N;
int A[MAX];
unordered_map<int, int> UM;
set<int> S;
set<int>::iterator IT;
int Answer;

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

void settings() {
    for (int i = 0; i < N; i++) {
        for (int j = (i + 1); j < N; j++) {
            if (UM[A[i] + A[j]] > 0) {
                int Count = UM[A[i] + A[j]];
                if (A[i] + A[j] == A[i]) {
                    Count--;
                }
                if (A[i] + A[j] == A[j]) {
                    Count--;
                }
                if (Count > 0) {
                    S.insert(A[i] + A[j]);
                }
            }
        }
    }
    for (IT = S.begin(); IT != S.end(); IT++) {
        int Now = *IT;
        Answer += UM[Now];
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}