2295번 : 세 수의 합 [C++]

문제 링크

성공 여부(걸린 시간): 성공 (36분 13초)

아이디어

이 문제는 이분탐색 또는 투포인터로 풀 수 있는 문제였는데 나는 문제를 보고

이분탐색에 대해서는 생각이 안났고 투포인터로 풀 수 있겠다고 생각해서 투포인터로 풀게 되었다.

 

우선 간단하게 생각하면 x, y, z 번째 수의 합으로 k번째 존재하는 수를 만들어낼 수 있다면 그의 최대값을 구하는 것이다.

처음에는 여러 방법에 대해서 생각하고 시간복잡도를 고려해보았다.

1. 세 수를 전부 정해놓고 탐색 (완전탐색)

• 방법: x, y, z를 전부 고정하고 가능한지 확인
• 반복문 3중 → O(N³)
• N이 1000이면
  → 1000³ = 10억 번 연산
  → 시간초과 확정

👉 현실적으로 불가능한 방법

---

2. 두 수를 정하고 나머지를 투포인터

• x, y 고정 → O(N²)
• z와 k를 투포인터로 조정 → O(N)
• 전체 → O(N³)

투포인터를 써도
결국 바깥이 이중 반복이면 전체는 여전히 세 겹 구조라서
👉 근본적으로 N³이라서 시간초과 위험

---

3. k를 큰 값부터 줄이면서 탐색 (현재 코드)

• k를 N번 탐색 → O(N)
• x를 0~k까지 → O(N)
• y, z를 투포인터 → O(N)

그래서 전체는 여전히

O(N³)

그런데 차이점은 👇

• 가장 큰 k부터 찾음
• 조건 만족하면 즉시 종료
• 평균적으로는 빨리 끝날 가능성 있음

👉 이론상은 N³
👉 하지만 최적화 + 조기 종료 덕분에 통과 가능성 있음

 

그래서 난 세번째 방법으로 코드를 작성했고 성공했다. 

풀이 코드

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    vector<int> set_u(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> set_u[i];
    }
    sort(set_u.begin(), set_u.end());

    for (int k = N - 1; k >= 0; k--) {
        for (int x = 0; x <= k; x++) {
            int y = x;
            int z = k;
            while (y <= z) {
                int sum = set_u[x] + set_u[y] + set_u[z];
                if (sum == set_u[k]) {
                    cout << sum;
                    return 0;
                }
                else if (sum < set_u[k]) {
                    y++;
                }
                else {
                    z--;
                }
            }
        }
    }
    cout << set_u[answer];
    return 0;
}