[백준] 5624-좋은 수

문제링크:https://www.acmicpc.net/problem/5624

5624번: 좋은 수

구현문제입니다. 기존의 방식대로 구현하면 a + b + c = d 를 구하는 문제이기 때문에  O(n^3)이기 때문에 당연히 시간 초과 입니다. O(n^2)만에 해결해야 합니다. 

방법은 a + b = d - c 로 변환 하여 해결하는 것입니다.

 

i번째마다 이전 두개의 값 조합(a + b)으로 (d - c)를 만들 수 있는지 판별하고,

i까지의 값들의 두개의 값 조합(a + b)을 추가해주며 진행됩니다.

 

아래는 정답코드입니다. 구현이전 까지의 설계가 어렵고 구현자체는 쉬운 문제였습니다. 

#include <iostream>
using namespace std;

int n = 0, result = 0;
int arr[5000] = { 0 };
bool r[400000] = { 0 };

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



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


	for (int i = 0; i < n; i++) {

		
	
		for (int j = 0; j < i; j++) { // a + b = d - c
			if (r[arr[i] - arr[j] + 200000]) {
				result++;
				//cout << arr[i] << endl;
				break;
			}
		}
		
		for (int j = 0; j <= i; j++) { // a + b check
			r[arr[i] + arr[j] + 200000] = 1;
		}
	}
	cout << result << endl;
}