백준 1253번 좋다(C++)

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

1253번: 좋다

 

 처음 봤을 때는 N이 그렇게까지 크진 않아서 그리디하게 풀이 가능하지 않을까 했는데 "두 개" 의 숫자로 나타낼 수 있음이 핵심이다. 

투포인터로 풀어야하는 문제이다.

1. 먼저 숫자를 정렬한다.

2. lo = 0 hi = n - 1로 설정하고 찾는 수 보다 크면 hi-- 작으면 lo++ 하며 범위를 좁힌다.

3. 예외 케이스는 0 0 1이다.

 

0 0 1 의 경우 그냥 투포인터로 잡아놓으면 3을 내놓는다. 0은 0, 1로 나타낼 수 없고 1은 0 0 으로 잡아낼 수 없다.

때문에 현재 lo hi가 i와 달라야한다. 이것만 주의하면 풀 수 있는 문제이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	vector<int> num;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		num.push_back(tmp);
	}
	sort(num.begin(), num.end());
	int answer = 0;
	for (int i = n - 1; i > -1; i--) {
		int hi = n - 1;
		int lo = 0;
		while (lo < hi) {
			if (num[i] == num[hi] + num[lo]) {
				if (hi != i && lo != i) {
					answer++;
					break;
				}		
				else {
					if (hi == i)
						hi--;
					else
						lo++;
				}
			}
			else if (num[i] > num[hi] + num[lo]) lo++;
			else hi--;
		}
	}

	cout << answer << '\n';
}