[백준 3273번] 두 수의 합

문제 링크:https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

 

<문제 풀이>

시간제한이 1초이고 N < 10^6 이므로 O(N^2) 풀이는 시간 초과입니다.

 

수열을 하나씩 꺼내보면서, 꺼낸 수와 합이 X가 되도록 하는 수열 내의 다른 어떤 수가 존재하는지 확인할 수 있으면 O(N)의 시간 복잡도로 문제를 해결할 수 있습니다.

 

수열에서 하나씩 꺼내서 X에서 뺀 뒤 그 수가 수열 내에 존재하는지 확인하면 됩니다.

-> a1 + a2 = X

    a2 = X - a1

 

문제 입력을 예로 들면

9

5 12 7 10 9 1 2 3 11

13

 

1) 5 -> 13(X) - 5 = 8 

2) 12 -> 13(X) - 12 = 1

3) 7 -> 13(X) - 7 = 6 

4) 10 -> 13(X) - 10 = 3

5) 9 -> 13(X) - 9  = 4

6) 1 -> 13(X) - 1  = 12

7) 2 -> 13(X) - 2  = 11

8) 3 -> 13(X) - 3  = 10

9) 11 -> 13(X) - 11  = 2

 

꺼낸 수가 등장한 수인지를 체크하는 배열을 만들고 입력받은 데이터를 순회하면서 

1. X - data가 이전에 등장했다면 카운트. 9) 11 -> 13(X) - 11 = 2  : 2는 7)에서 등장한 수로 체크함

2. 꺼낸 수는 등장한 수 배열에 체크해줍니다.  

 

X - data가 음수가 나올 수도 있음(배열 런타임 에러)

 

<C++ 소스 코드>

#include <iostream>
#include <vector>
using namespace std;
 
bool flag[2000001];
 
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    vector<int> v;
    int n; cin>>n;
    for(int i=0; i<n;i++){
        int data; cin>>data;
        v.push_back(data);
    }
    int x; cin>>x;
    
    int cnt = 0;
 
    for(auto &data : v){
        if(x >= data && flag[x - data]) cnt++;
        flag[data] = true;
    }
    cout<<cnt;
    
    return 0;
}