[3273번] 두 수의 합

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 수학

2. map STL

Ai + Aj = m 이어야 한다.

결국 m - Aj = Ai이어야 한다.

따라서 우리는 A 배열을 보며 m - Aj를 할 때 Ai가 있는지만 보면 된다.

아래 코드에서 

        if (m > here && mp[m - here] && m - here != here)

        {

            cnt++;

            mp[m - here] = 0;

        }        

이 부분에 대한 설명은 다음과 같다.

1. m이 항상 Aj보다 커야하니 m > here 조건이 있다.

2. m - Aj = Ai 즉, m - Aj을 했을 때 Ai가 존재하는지 보고 있는 상황이다.

3. m - here != here의 의미는 다음 테스트 케이스를 위한 것이다.

2

1 2

2

이때 m - Aj -> 2 - 1 = 1이 되어 자기자신을 보고있는 결과가 생긴다. 따라서 자기 자신을 보고 있는 것을 제외시켜 준다.

(자기자신을 본다는 것은 1 + 1 = 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

#include <iostream> #include <cstdio> #include <map>   using namespace std;   map<int, bool> mp;   int main() {     int n;     scanf("%d", &n);       for (int i = 0; i < n; i++)     {         int val;         scanf("%d", &val);         mp[val] = true;     }       int m;     int cnt = 0;     scanf("%d", &m);       for (auto it = mp.begin(); it != mp.end(); it++)     {         if (it->second == 0)             continue;           int here = it->first;           if (m > here && mp[m - here] && m - here != here)         {             cnt++;             mp[m - here] = 0;         }             }     printf("%d", cnt);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus