BOJ_2467
😄 밑에 초등부 문제라고 써있다. 어나더 레벨의 친구들이 풀었나보다.
2467번 : 용액
- N개의 용액 중에 2개를 뽑아 0과 가장 가까운 수를 만들면 되는 문제이다.
- 하나씩 모두 비교하는 2중 For문을 사용하면 N^2의 시간복잡도가 생겨난다.(10만 * 10만)
- 그래서 나는 For문을 단 한번 N의 시간복잡도로 풀 수 있는
두 포인터
를 생각했다. - 인덱스를 가장 앞과 가장 뒤에 하나씩 배치하고 인덱스에 따른 수 두개를 더했을 때
- 잠깐!!
두 포인터
를 쓰려면 오름차순 정렬부터 해준다. - 양수가 나오면? 양수의 힘이 세니깐 오른쪽의 인덱스를 낮춰준다.
- 음수가 나오면? 음수의 힘이 세니깐 왼쪽 인덱스를 높여준다.
- 0이 나오면? 무조건 나간다. 0이 되면 그게 답!!
- 잠깐!!
💻 두 포인터
int start = 0, end = N - 1, result = 2000000000;
int resultx, resulty;
while (start < end)
{
int sum = v[start] + v[end];
if (abs(sum) < abs(result))
{
result = sum;
resultx = v[start];
resulty = v[end];
}
if(sum > 0)
end -= 1;
else if(sum < 0)
start += 1;
else if(sum == 0)
break;
}
if(abs(num) < abs(result))
구문은 답을 찾기 위한 if문이다.
💻 전체 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string.h>
using namespace std;
#define endl "\n"
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
vector<int> v;
cin >> N;
for (int i = 0; i < N; i++)
{
int num;
cin >> num;
v.push_back(num);
}
sort(v.begin(), v.end());
int start = 0, end = N - 1, result = 2000000000;
int resultx, resulty;
while (start < end)
{
int sum = v[start] + v[end];
if (abs(sum) < abs(result))
{
result = sum;
resultx = v[start];
resulty = v[end];
}
if(sum > 0)
end -= 1;
else if(sum < 0)
start += 1;
else if(sum == 0)
break;
}
cout << resultx << " " << resulty << endl;
}
😳
두 포인터
에 대해서 알고 있다면 쉽게 풀수 있는 문제지만 그렇지 않다면 조금은 어려울 수도 있을 문제다.
Author And Source
이 문제에 관하여(BOJ_2467), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@luck2901/BOJ2467저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)