백준 BOJ 2295 - 세 수의 합

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

2295번: 세 수의 합

말이 세 수의 합이지 브루트포싱하면 O(N^4)이다...

세 수의 합 d와 배열 안의 어떤 수 U가 같아지는 경우를 찾아야 한다.

브루트포스로 접근했을 때 세 수가 O(N^3), U와 매칭시키면서 O(N)이므로

전체 시간복잡도가 O(N^4)가 되어서 시간초과를 받는다.

 

밋인더미들 알고리즘을 사용해서 선택해야하는 네 수 (세 수 a,b,c 와 U) 를

두 묶음으로 분리해 (a,b), (c,U) 로 봐줘야 한다.

 

a와 b를 더해서 가능한 모든 합을 만드는데 O(N^2),

c와 U를 선택해서 앞서 구한 N^2개의 합과 비교대조해보는데 O(N^2logN)이 되도록

프로그램을 작성해주면

제한시간 내에 문제를 해결할 수 있다.

 

두가지 방법이 있는데

첫번째는 a+b의 합을 std::map에 저장해서 관리해주는거고

두번째는 이분탐색을 사용해서 a+b를 찾아내는 것이다.

둘중 어느경우라도 시간복잡도가 동일하므로 문제를 해결할 수 있다.

나는 std::map을 사용했다.

 

전체 시간복잡도 O(N^2logN)

 

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

ll arr[1234] = {0};
map<ll,int> m;


int main(){
	int N;
	cin >> N;
	for(int i=0; i<N; i++) cin >> arr[i];
	
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			m[arr[i]+arr[j]] = 1;
		}
	}
	
	ll ans = 0;
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			if(m.find(arr[j]-arr[i]) != m.end()){
				ans = max(ans, arr[j]);
			}
		}
	}
	cout << ans;
	return 0;
}