CSES 2. Sum of Three Values (1641)

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

---

문제 설명

You are given an array of n integers, and your task is to find three 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 three integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

입력 예

4 8
2 7 5 1

출력 예

1 3 4

제약조건

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

---

문제 풀이 

첫번째 수를 고정하고, 필요한 수에서 그 수만큼을 빼내면, n-1 배열에서 2개의 합으로 (x - a_i)를 만드는 문제가 된다. 참고

프로그램 내용

...
    vector <pair <long, long> > num_arr;

    for(int idx=0; idx < nNum; ++idx)
        int temp;
        num_arr.push_back({temp, idx+1});

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

    for (int a=0; a < nNum-2; ++a)
        int b = a+1 , c = nNum-1;
        int ttSum = tSum - num_arr[a].first;
        while( b < c )
            int k = num_arr[b].first + num_arr[c].first;

            if (k == ttSum)
                cout << num_arr[a].second << " " << num_arr[b].second << " " << num_arr[c].second << endl;
            else if ( k < ttSum) b++;
            else c--;
...

 

Sorting and Searching ( link )