[백준 / C++] 2295번 세 수의 합 풀이

---

처음 문제를 읽었을 때는 N의 개수가 최대 1000개니 sorting한 이후 3개씩 슬라이딩 윈도우로 브루트포스 방식을 취하면 풀리지 않을까 생각하였으나, 슬라이딩 한 것들을 다시 확인 하는 방법에서 막혔고 다시보니 중복되게 선택할 수 있었다.

 

이후 map을 이용해 for문 3개 중첩을 무지성으로 시도하다 생각해보니 N³logN 이라 시간 초과 문제가 생겼다.

(1000개를 3제곱하면 최소 10억이라 10초다.

심지어 map은 메모리 초과문제도 생겨 set으로 변경하였다)

 

더 이상 줄일 방법을 찾지 못해 힌트를 보았다가 다들 천재인가 싶었다.

풀이 방법은 간단하다.

 

1.  x,y,z 를 따로 구하지 않고 y,z를 합으로 한 배열(sum)을 하나 생성한다 (N²)
2. 기존 배열을 arr라고 가정했을 때 x + y + z = arr[?] 로 특정 원소이므로, y+z = arr[?] - x 이다.
3. y+z라는 배열을 구했으니 배열(sum) 내에서 특정 원소끼리의 차가 새로 구한 배열에 있다면 세 수의 합이 존재하는 것이다.
4. 배열 내에 존재하는지 set을 이용하여 이분탐색.

이 방법으로 풀어내면  N² + N² * log(N) 이므로 시간 내에 해결할 수 있다.

---

#include <bits/stdc++.h>
using namespace std ;
int N, maxima ;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0) ;
    cin >> N ;
    vector<int> arr(N) ;
    set<int> sum ;

    for(int &it : arr)
        cin >> it ;
    
    for(int i = 0 ; i < N ; i++)
        for(int j = 0 ; j < N ; j++)
            sum.insert(arr[i] + arr[j]) ;
    
    for(int k = 0 ; k < N ; k++)
        for(int x = k ; x < N ; x++)
            if(sum.count(arr[x] - arr[k])) maxima = max(maxima, arr[x]) ;
    
    cout << maxima << '\n' ;

}

---

느낀점: 진짜 풀이 방법에 다양하게 벽을 느낀다.

 

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

2295번: 세 수의 합