반응형
<문제 링크>
https://www.acmicpc.net/problem/2467
<알고리즘 분류>
- 투 포인터(Two Pointer)
- 이분 탐색(Binary Search)
<풀이>
간단한 투 포인터 문제로 보인다. 과정은 이러하다.
(1) 용액 배열의 양 끝을 초깃값으로 잡은 뒤, 서로 다가오면서(투포인터) 두 개의 합이 0에 가장 가까울 경우 저장해준다.
(2) 두 개의 합이 0 보다 작을 경우, 조금 더 0보다 가까운 경우가 있는지 알아보기 위해 left++를 해준다.
(3) 두 개의 합이 0보다 클 경우, 조금 더 0보다 가까운 경우가 있는지 알아보기 위해 right--를 해준다.
<코드>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
long long liquid[100001];
int main()
{
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> liquid[i];
}
int l = 0;
int r = N - 1;
int min_r, min_l;
int result = liquid[r] + liquid[l];
while (r > l)
{
if (abs(result) >= abs(liquid[l] + liquid[r]))
{
result = liquid[r] + liquid[l];
min_r = r;
min_l = l;
}
if (liquid[l] + liquid[r] < 0)
l++;
else
r--;
}
cout << liquid[min_l] << " " << liquid[min_r] << "\n";
return 0;
}
반응형
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[C++] 백준 2143 - 두 배열의 합 (0) | 2023.09.03 |
---|---|
[C++] 백준 12015 - 가장 긴 증가하는 부분 수열 2 (0) | 2023.08.28 |
[C++] 백준 1253 - 좋다 (2) | 2023.08.28 |
[C++] 백준 2110 - 공유기 설치 (0) | 2023.08.28 |
[C++] 백준 1450 - 냅색문제 (0) | 2023.08.26 |
반응형
<문제 링크>
https://www.acmicpc.net/problem/2467
<알고리즘 분류>
- 투 포인터(Two Pointer)
- 이분 탐색(Binary Search)
<풀이>
간단한 투 포인터 문제로 보인다. 과정은 이러하다.
(1) 용액 배열의 양 끝을 초깃값으로 잡은 뒤, 서로 다가오면서(투포인터) 두 개의 합이 0에 가장 가까울 경우 저장해준다.
(2) 두 개의 합이 0 보다 작을 경우, 조금 더 0보다 가까운 경우가 있는지 알아보기 위해 left++를 해준다.
(3) 두 개의 합이 0보다 클 경우, 조금 더 0보다 가까운 경우가 있는지 알아보기 위해 right--를 해준다.
<코드>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
long long liquid[100001];
int main()
{
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> liquid[i];
}
int l = 0;
int r = N - 1;
int min_r, min_l;
int result = liquid[r] + liquid[l];
while (r > l)
{
if (abs(result) >= abs(liquid[l] + liquid[r]))
{
result = liquid[r] + liquid[l];
min_r = r;
min_l = l;
}
if (liquid[l] + liquid[r] < 0)
l++;
else
r--;
}
cout << liquid[min_l] << " " << liquid[min_r] << "\n";
return 0;
}
반응형
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[C++] 백준 2143 - 두 배열의 합 (0) | 2023.09.03 |
---|---|
[C++] 백준 12015 - 가장 긴 증가하는 부분 수열 2 (0) | 2023.08.28 |
[C++] 백준 1253 - 좋다 (2) | 2023.08.28 |
[C++] 백준 2110 - 공유기 설치 (0) | 2023.08.28 |
[C++] 백준 1450 - 냅색문제 (0) | 2023.08.26 |