백준 2295 세 수의 합 (c++) : 피너클

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

 

투포인터로 풀었다.

int n;
unordered_map<int, int> visited;
int arr[1001];
int sum[1000001];
int len = 0;

선언 변수들이다.

 

n = 1000 이므로 삼중 반복문을 돌리면 시간이 1000 ^ 3이 되어버려 제한시간안에 끝내지 못한다.

그렇기에 이전에 arr에서 합을 따로 하나 구해놓을 것이다. 그것이 sum이다.

visited는 sum안에 겹치는 숫자가 들어가지 않게 해준다.

len은 sum의 길이다.

 

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

    sort(arr, arr + n);

값들을 입력받은뒤 정렬해준다. 반드시 정렬해줘야햔다.

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int s = arr[i] + arr[j];
            if (visited[s] == 0) {
                visited[s] = 1;
                sum[len++] = s;
            }
        }
    }

그후 arr의 합을 sum에 넣어준다. visited로 값이 겹치지 않게 해준다.

   sort(sum, sum + len);

그후 정렬해준다.

    for (int i = n - 1; i >= 0; i--) {
        int target = arr[i];

        int start = 0, end = len - 1;

이제 높은 숫자부터 검사할것이다.

target을 가장 높은 숫자부터 잡아준다.

start는 arr에서 사용할 포인터로 가장 낮은 숫자부터 올라갈것이며

end는 sum에서 사용할 포인터로 가장 높은 숫자부터 내려갈것이다.

        while (start < n && end >= 0) {
            int a = arr[start], s = sum[end];
            int m = a + s;

start와 end 각각이 배열 안의 범위 안에 있을때만 반복한다.

m에는 숫자의 합을 넣어준다.

            if (m == target) {
                cout << m << endl;
                return 0;
            }
            else if (m > target) end--;
            else start++;
        }
    }

그 후엔 m이 target과 같으면 출력해주고 

m이 target보다 크면 end--해주고 아니면 start++ 해준다.

 

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int n;
unordered_map<int, int> visited;
int arr[1001];
int sum[1000001];
int len = 0;

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

    sort(arr, arr + n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int s = arr[i] + arr[j];
            if (visited[s] == 0) {
                visited[s] = 1;
                sum[len++] = s;
            }
        }
    }
    sort(sum, sum + len);
    for (int i = n - 1; i >= 0; i--) {
        int target = arr[i];

        int start = 0, end = len - 1;
        while (start < n && end >= 0) {
            int a = arr[start], s = sum[end];
            int m = a + s;

            if (m == target) {
                cout << m << endl;
                return 0;
            }
            else if (m > target) end--;
            else start++;
        }
    }

    return 0;
}

전체코드다.