[백준]3273번 두 수의 합 c/c++

문제

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

3273번: 두 수의 합

 

코드

 

#include<iostream>
using namespace std;


int arr[1000001]; // 수열의 크기
bool vis[2000001]; //방문했는지 표시
int main()
{
	int n;
	cin >> n;

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

	int x;
	cin >> x;

	int count = 0;
	for (int i = 0; i < n; i++) {
		if (x - arr[i] > 0 && vis[x - arr[i]]) { //x에서 수열을 뺀 값이 이미 방문했다면, 쌍이 있다는뜻!! (쌍이 존재하는지 매번 확인)
			count++;
		}
		vis[arr[i]] = 1; //true (모든 수열을 방문했다고 표시)
	}
	cout << count;
	return 0;
}

 

설명

 

수열의 크기는 최대 1,000,000 이므로 arr 배열의 크기를 1,000,001로 설정해두었다.

그리고 x는 1보다 크거나 같고 2,000,000보다 같거나 작으므로 2,000,001로 설정해두었다.

 

수열을 하나하나 검토해가면서 방문했다고 표시해주고

만약에 x에서 수열의 값을 뺀 값이 이미 방문했다고 하면 조건을 만족하는 쌍의 수가 있다는 말이므로

count값을 늘려준다!

 

이 경우엔 (1, 12), (3, 10), (11, 2) 이렇게 합이 13이 되는것이 3쌍이 있기 때문에 count값이 3이다.

 

배열을 활용하여 이렇게 푸는 방법이 있다는걸 익혀두는게 중요한것같다.