백준 3273 두 수의 합 c++

 

 

 

처음 작성한 코드는 다음과 같다.

하지만 시간 초과 오류가 났다. 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    
    vector<int> arr(n);
    for(int i=0; i<n; i++)
        cin >> arr[i];
    
    int x;
    cin >> x;
    
    sort(arr.begin(), arr.end());
    
    int count = 0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            if(arr[i]+arr[j] == x){
                count++;
                break;
            }
        }
    }
    
    cout << count;
    return 0;
}

 

 

 

다시 작성한 코드는 다음과 같다.

exist[arr[i]] = true; 의 위치가 중요했다.

처음엔 그냥 arr[i]값을 입력받아올때 exist배열도 같이 exist[arr[i]] = true; 로 초기화했다.

하지만 문제에서는 i < j일때 arr[i] + arr[j]가 되는 경우를 원했다. 

exist[arr[i]] = true; 가 꼭 for문안에 저렇게 들어가야 했다.

저기에 있지 않고 먼저 초기화해버리면 5+7인경우랑 7+5인 경우를 모두 계산하게 된다. (중복 발생)

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    int arr[100001];
    bool exist[2000001];
    for (int i=0; i<n; i++) {
        cin >> arr[i];
    }

    int x;
    cin >> x;

    int answer = 0;
    for (int i=0; i<n; i++) {
        if (x-arr[i] > 0 && exist[x-arr[i]]) 
            answer++;
        exist[arr[i]] = true;
    }

    cout << answer;
    return 0;
}