[BOJ] 1253번 좋다 (C++)

문제 (https://www.acmicpc.net/problem/1253)

1253번: 좋다

처음엔 검사하는 숫자보다 작은 수들로만 검사하는 숫자가 만들어진다고 생각했다. 하지만 음수도 가능하기 때문에 -4 -2 -2 같은 케이스가 존재한다. (-4가 좋은 수) 

또한 자기 자신은 서로 다른 두 수에 해당하면 안 되므로 예외 처리를 해주어야 한다. 나는 그냥 for문을 돌 때마다 원본 벡터를 복사한 벡터에 해당 숫자를 erase로 제거하여 사용했다.

 

- n이 2보다 작거나 같으면 다른 수 두 개의 합으로 나타낼 수 없으므로 0을 출력하고 종료한다.

- 입력받은 수들을 오름차순 정렬한다.

- 복사본 벡터에서 i번째 숫자를 제거한다. (erease 함수)

- 투 포인터로 i번째 숫자가 좋은 수가 될 수 있는지 확인한다.

---

[소스코드]

	/*
	BOJ 1253번: 좋다
	2022-01-18
	Two pointers
	*/
	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	vector<int> vec;
	int n, input;
	int start, end;
	int ans = 0;
	cin >> n;
	for(int i = 0 ; i < n ; i++) {
	cin >> input;
	vec.push_back(input);
	}
	if(n <= 2) {
	cout << 0;
	return 0;
	}
	sort(vec.begin(), vec.end());
	for(int i = 0 ; i < n ; i++) {
	vector<int> cp = vec;
	cp.erase(cp.begin() + i);
	start = 0; end = n - 2;
	while(start < end) {
	int sum = cp[start] + cp[end];
	if(sum == vec[i]) {
	ans++;
	break;
	}
	if(sum < vec[i]) start++;
	else end--;
	}
	}
	cout << ans;
	return 0;
	}

view raw 1253.cpp hosted with ❤ by GitHub

---

2022-01-18

Gold 4

- 자료 구조

- 정렬

- 이분 탐색

- 해시를 사용한 집합과 맵

- 두 포인터