https://www.acmicpc.net/problem/9024
9024번: 두 수의 합
프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄
www.acmicpc.net
배열에서 합이 K에 가장 가까운 서로 다른 두 개의 정수 조합의 갯수를 구하는 문제입니다.
이 문제는 투 포인터를 이용하여 해결할 수 있습니다.
투 포인터 사용을 위해 배열을 오름차순으로 정렬합니다.
그리고 left = 0, right = N - 1에서 시작합니다.
두 정수의 합(list[l] + list[r])이 K에 더 가까우면 합(ans)을 갱신, 갯수를 의미하는 cnt를 1로 초기화합니다.
만약 두 정수의 합과 갱신된 합이 같으면 cnt를 1 증가합니다.
그리고 두 정수의 합이 K보다 크면 값을 작게 해야하므로 right를 1 감소,
두 정수의 합이 K보다 작으면 값을 크게 해야하므로 left를 1 증가시킵니다.
최종으로 K에 가장 가까운 두 정수의 조합의 갯수인 cnt를 출력합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
#include <iostream>
#include <algorithm>
#define MAX 1000000
using namespace std;
int list[MAX];
int N, K;
void func() {
int l = 0;
int r = N - 1;
int ans = 2e8;
int cnt = 0;
while (l < r) {
int sum = list[l] + list[r];
if (abs(sum - K) < abs(ans - K)) {
ans = sum;
cnt = 1;
}
else if (abs(sum - K) == abs(ans - K)) {
cnt++;
}
if (sum > K) r--;
else l++;
}
cout << cnt << '\n';
}
void input() {
cin >> N >> K;
for (int i = 0; i < N; i++) {
cin >> list[i];
}
sort(list, list + N);
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
int tc;
cin >> tc;
while (tc--) {
input();
func();
}
return 0;
}
|
cs |
'algorithm > Two-Pointer' 카테고리의 다른 글
| boj 1253 좋다 (0) | 2021.10.21 |
|---|---|
| boj 17609 회문 (0) | 2021.03.29 |
| boj 2559 수열 (0) | 2021.02.12 |
| boj 1806 부분합 (0) | 2021.01.22 |
| boj 2003 수들의 합 2 (0) | 2021.01.22 |