[c/c++] BOJ 3273번 -두 수의 합

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

3273번: 두 수의 합

문제

문제 풀이

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


//두 수의 합
//n개의 서로 다른 양의 정수 a1,a2,a3---an으로 이루어진 수열이 있음.
//ai의 값은 1보다 크거나 같고, 1,000,000보다 작거나 같은 자연수.
//자연수 ai + aj = X을 만족하는 (ai,aj) 쌍의 수를 구하시오.
int main(){
    ios::sync_with_stdio(0);
	cin.tie(0);

    //수열의 크기
    int n;
    cin >> n;
    //수열에 포함되는 수
    int array[1000001];
    int resultArr[2000001];
    for(int i=0;i<n;i++){
        cin >> array[i];
    }
    
    //X의 값
    int x;
    cin >> x;

    int count=0;
    
    //시간 복잡도 O(N)을 가지고 있음.
    for(int i=0;i<n;i++){
        //x-array[i]가 양수여야 함.
        if((x-array[i]) > 0){
            if(resultArr[x-array[i]] == 1){
                count++;
            }else{
                resultArr[array[i]]=1;
            }
        }
    }

    cout << count;

}

문제의 포인트.

배열과 관련된 문제.

조건

• 1 <= N <=100000 의 범위이고 1<= X < =2000000의 범위 입니다.
• x-array[i]의 값이 0보다 크고 resultArr[x-array[i]]의 값이 1이면 count를 1 증가 시킵니다. 
• x-array[i]의 값이 0보다 크지만 resultArr[x-array[i]]의 값이 1이 아니면 값을 1로 세팅해 주고 다음으로 넘어갑니다.