[C++] 백준/Gold/1253. 좋다

문제: 좋다 (백준 1253번)

문제 분석

이 문제는 주어진 수열에서 "좋은 수"의 개수를 찾는 문제이다.

• 정의:
  수열의 한 원소가 다른 두 원소의 합으로 표현될 수 있다면, 그 원소를 "좋은 수"라고 한다.
• 제한:
  • 한 원소는 자기 자신을 이용할 수 없다.
  • 같은 원소의 인덱스가 겹치면 안 된다.

문제의 핵심은 모든 가능한 두 원소의 합을 고려해, 해당 합이 수열 내의 다른 원소와 일치하는지 확인하는 것이다.

---

해결 방법

1. 자료구조 준비:
   • 벡터 v: 입력받은 수들을 저장.
   • 딕셔너리 dict: 각 숫자에 대해 (인덱스, 상태)를 저장하는 unordered_map 사용.
     • 키: 해당 숫자
     • 값: 해당 숫자가 등장하는 인덱스와, 아직 "좋은 수" 후보로 남아있는지를 나타내는 불리언 값
       → true: 아직 후보
       → false: 이미 한 번 사용하여 "좋은 수"로 판별됨
2. 두 원소의 합 탐색:
   • 모든 가능한 두 원소 $(v[i],v[j])$ (단, $i<j$)의 합을 계산한다.
   • 이 합(key)이 딕셔너리에 존재하는지 확인한다.
   • 만약 존재하면, 해당 키에 매핑된 벡터를 순회하며,
     • 인덱스가 $i$ 또는 $j$ 와 겹치지 않고,
     • 아직 후보 상태(true)라면 "좋은 수"로 판별하고, 상태를 false로 변경한 후,
     • 후보 수를 세어준다.
3. 중복 처리:
   • 한 번 "좋은 수"로 판별된 원소는 이후 다시 카운트하지 않도록,
   • 해당 원소를 다시 후보 목록에서 제거(혹은 상태를 false로 변경)하여 중복 계산을 피한다.

---

코드 전체

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
    
    int n; 
    cin >> n;
    
    // dict: 숫자를 key로, 해당 숫자의 인덱스와 사용 여부(bool)를 저장
    unordered_map<int, vector<pair<int, bool>>> dict;
    vector<int> v(n);
    int answer = 0;

    // 입력: 숫자와 인덱스 저장
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        dict[v[i]].push_back({i, true});
    }

    // 모든 가능한 두 원소 (i, j) 선택 (i < j)
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            int key = v[i] + v[j]; // 두 원소의 합
            // dict에 key가 존재하는 경우 검사
            if (dict.contains(key))
            {
                auto& vec = dict[key];
                vector<pair<int, bool>> new_vec;
                // key에 해당하는 모든 후보들에 대해
                for (pair<int, bool>& p : vec)
                {
                    // 이미 사용되지 않았고, 인덱스가 i, j와 겹치지 않으면
                    if (p.second && p.first != i && p.first != j)
                    {
                        p.second = false; // 이미 "좋은 수"로 판별됨
                        answer++;
                    }
                    // 아직 후보인 경우, new_vec에 유지
                    if (p.second) new_vec.push_back(p);
                }
                // 업데이트된 벡터로 교체하여 이후 불필요한 탐색을 줄임
                vec = move(new_vec);
            }
        }
    }

    cout << answer;
}