C++ 알고리즘 - 백준 3273 두 수의 합

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

 

 

알고리즘 공부를 전혀 하지 않고 순수 개발 실력으로만 했더니 이런 처참한 결과가..

결국 고민 끝에 해결방법을 찾았다.

 

 

#include <iostream>
using namespace std;

int num[100000];
int chk[2000001] = { 0 };

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int size;
	int value;
	int cnt = 0;

	cin >> size;

	for (int i = 0; i < size; i++) {
		cin >> num[i];
		chk[num[i]] = 1;
	}

	cin >> value;

	for (int i = 0; i < size; i++) {
		if (value - num[i] > 0 && chk[value - num[i]] != 0)
			cnt++;
	}

	cout << cnt / 2;

	return 0;
}

 

눈여겨봐야 할 부분은

cin으로 값을 입력 받을 때 chk[num[i]]의 값에 1을 주고

값을 검증 할 때 chk[value-num[i]]의 값이 1인지 판단한다.

 

예를 들어,

num[0]의 값으로 18을 줬다면

chk[18]의 값에 1이 들어간 것이고

 

value가 33, num[i]가 15일때, 33-15 = 18

즉 chk[18]의 값이 1인 경우 배열에 쌍을 이루는 값이 있다는 것으로 판단한다.

 

마지막으로 중복 값이 발생하였으므로 /2 해주면 정답이다.

 

 

P.S. 투포인터 방식도 있다고 하는데 알고리즘 공부를 하고 재도전 해봐야겠다.