문제
풀이
- 2중 for문을 돌려서 정답을 찾으면 시간 초과가 발생한다. 두 포인터 알고리즘을 이용한다.
- 용액의 입력값이 오름차순으로 입력된다. 용액 vector의 양쪽에서 부터 start와 end로 시작하여 검사한다.
- start가 end의 값을 넘을 때까지 검사하며, start와 end의 합의 절댓값이 현재 answer보다 작다면 갱신한다.
- start와 end의 합의 부호에 따라 start와 end의 값을 증가하거나 감소시킨다.
코드
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main()
{
int N;
vector<int> v;
vector<int> answer;
cin >> N;
v.resize(N);
answer.resize(2);
for (int i = 0; i < N; ++i)
{
cin >> v[i];
}
int start = 0;
int end = N - 1;
answer[0] = v[start];
answer[1] = v[end];
// vector의 양쪽에서 다가오면서 start가 end를 넘어설 때 까지 검사
while (start < end)
{
// 현재 start와 end의 합의 절댓값이 answer의 절댓값보다 작다면 갱신
if (abs(answer[0] + answer[1]) > abs(v[start] + v[end]))
{
answer[0] = v[start];
answer[1] = v[end];
}
// 합이 0보다 작다면 음수의 절댓값이 크므로 start를 1증가
if (v[start] + v[end] < 0)
{
start++;
}
else
{
end--;
}
}
cout << answer[0] << " " << answer[1];
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준][C++] 1197: 최소 스패닝 트리 (0) | 2023.10.09 |
---|---|
[백준][C++] 27172: 수 나누기 게임 (1) | 2023.10.08 |
[백준][C++] 2166: 다각형의 면적 (0) | 2023.10.06 |
[백준][C++] 13172: Σ (0) | 2023.10.05 |
[백준][C++] 2448: 별 찍기 - 11 (0) | 2023.10.04 |