8046 : 세 수의 합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
크기가 $N$인 정수 배열과 목표 합 $X$가 주어집니다.
배열에서 서로 다른 세 위치(인덱스)의 원소를 선택하여 그 합이 정확히 $X$가 되도록 하는 프로그램을 작성하시오.
[제약 조건]
• $1 \le N \le 5{,}000$
• $1 \le X \le 10^9$
• $1 \le x_i \le 10^9$
배열에서 서로 다른 세 위치(인덱스)의 원소를 선택하여 그 합이 정확히 $X$가 되도록 하는 프로그램을 작성하시오.
[제약 조건]
• $1 \le N \le 5{,}000$
• $1 \le X \le 10^9$
• $1 \le x_i \le 10^9$
입력 설명
첫째 줄에 배열의 크기 $N$과 목표 합 $X$가 공백으로 구분되어 주어집니다. ($1 \le N \le 5000$, $1 \le X \le 10^9$)
둘째 줄에 $N$개의 정수 $x_1, x_2, \ldots, x_N$이 공백으로 구분되어 주어집니다. ($1 \le x_i \le 10^9$)
둘째 줄에 $N$개의 정수 $x_1, x_2, \ldots, x_N$이 공백으로 구분되어 주어집니다. ($1 \le x_i \le 10^9$)
출력 설명
조건을 만족하는 서로 다른 세 원소의 원래 인덱스(1-based)를 공백으로 구분하여 오름차순으로 출력합니다. 만약 그러한 세 수가 존재하지 않는다면
IMPOSSIBLE을 출력합니다. (답이 여러 개일 경우 아무거나 출력해도 인정됩니다.)
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 8
2 7 5 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 3 4도움
정렬 후 투 포인터(Two Pointers) 기법을 활용해 $O(N^2)$ 시간에 해결할 수 있습니다.
배열의 원소들을 원래 인덱스와 쌍으로 묶어 값 기준으로 정렬합니다. 1번째 원소
배열의 원소들을 원래 인덱스와 쌍으로 묶어 값 기준으로 정렬합니다. 1번째 원소
i를 고정하고, 나머지 구간의 양끝을 l = i + 1, r = N - 1 포인터로 설정한 뒤 arr[l] + arr[r]의 합을 비교해가며 두 포인터를 좁힙니다. 합이 부족하면 l을 키우고, 목표 합을 초과하면 r을 줄이는 루프로 $O(N^2)$ 알고리즘을 설계할 수 있습니다.