CSES 2. Sum of Four Values (1642)

출처: https://cses.fi/problemset/task/1642

---

문제 설명

You are given an array of n integers, and your task is to find four values (at distinct positions) whose sum is x.

입력 

The first input line has two integers n and x: the array size and the target sum.

The second line has n integers a_1,a_2,…,a_n: the array values.

출력 

Print four integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

입력 예

8 15
3 2 5 8 1 3 2 3

출력 예

2 4 6 7

제약조건

• 1 <= n <= 1000
• 1 <= x, a_i <= 10^9

---

문제 풀이 내용

서로 다른 배열의 원소 2개의 합으로 새로운 배열을 만든다. 그러면 배열에서 2개의 합으로 원하는 수를 만드는 문제로 바꿀 수 있다. (참고) 다만, 원래 배열에서 4개의 원소가 달라야 하는 조건을 확인해야 한다.

프로그램 내용

...
    vector <tuple <long, int, int> > num_arr;

    for(int idx=0; idx < nNum; ++idx)
        int temp;
        in_num.push_back(temp);

    for(int idx=0; idx < nNum-1; ++idx)
        for(int id = idx+1; id < nNum ; ++ id)
            num_arr.push_back(make_tuple(in_num[idx]+in_num[id], idx+1, id+1));

    sort(num_arr.begin(), num_arr.end());

    int id = 0, idx = num_arr.size()-1;
    while( id < idx )
        long a, b, c, d, e, f;
        tie(a, b, c) = num_arr[id];
        tie(d, e, f) = num_arr[idx];
        long k = a+d;

        if (k == tSum)
            if ( b == e || c == f)
                break;
            else
                cout << b << " " << c << " " << e << " " << f << endl;
        else if ( k < tSum) id++;
        else idx--;
...

 

Sorting and Searching ( link )