[맞음] 백준 3273 cpp // 두수의 차 visited 배열활용, 투포, 이분탐색

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

3273번: 두 수의 합

* 기본개념

1. 목표가 100이고, 20이 현재값이면 

visited[80]이 true -> 정답이 가능하다.

 

* 에러

out of bounds 

원인 : visitied[x-v[i]]

해결 : x가 최대 20만 이므로 visited도 20만으로 선언

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

int n, x, visited[2000004], ret;
vector<int> v;

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int temp = 0;
		cin >> temp;
		v.push_back(temp);
		visited[temp] = 1;
	}
	cin >> x;

	for (int i = 0; i < n; ++i) {
		if (x < v[i]) continue;
		//목표보다 현재값이 큰경우 -> 불가

		if (visited[x - v[i]]) { //목표값이 잇으면 ret++
			ret++;
			//cout << "v[i] : 목표값 " << v[i] << " " << x - v[i]<<endl;
		}
		else {
			//pass
		}
	}

	cout << ret / 2;	//(1,3) 과 (3,1)을 중복처리제거.

}

 

* 25.1.30. 2회독

• lower_bound 값 찾았는지 확인방법

 

 

* 큰돌

• 예시로 관찰하면서 >, < , = 포인터 어떻게 가는지 탐색
• 삼각형 그림을 많이 그린다.