안녕하세요! 테크지니어입니다.
오늘은 백준 알고리즘 2467번 용액 문제를 풀어보도록 하겠습니다.
https://www.acmicpc.net/problem/2467
2467번: 용액
첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -
www.acmicpc.net
[문제접근]
시간제한은 1초이고, N은 10만이하이기 때문에 N^2은 100억이 되어 완전탐색은 시간초과가 발생합니다.
1차원 배열에서 특정 두 개의 용액을 찾는 문제라는 점에서 투 포인터를 떠올릴 수 있고, 정렬된 순서로 주어졌다는 점에서 이분 탐색까지 떠올릴 수 있습니다.
[풀이전략]
(1) 투 포인터 풀이
1. 가장 자리부터 확인하기 위해 st = 0, en = n-1로 초기화한다.
2. 절대값이 가장 작은 합 특성값을 저장할 변수 minTot 을 큰 값으로 초기화한다.(용액MAX * 2 + 1, 넉넉히 1을 더함)
3. sum = arr[st]+arr[en]의 절댓값이 minTot의 절대 값보다 작으면 minTot에 대입하고, 두 용액을 저장한다.
4. sum이 0보다 크면 en을 한 칸 감소시키고, 0보다 작으면 st를 한 칸 증가시킨다. 0과 같으면 풀이를 종료한다.
5. st랑 en이 다를 때까지 while문을 이용하여 상황을 반복한다.
(2) 이분 탐색 풀이
1. 순차적으로 용액을 하나 선택한다. for문 이용
2. 그 용액의 특성값*(-1)을 lower_bound를 이용하여 찾는다. (lower_bound는 원하는 값과 같은 혹은 큰 것들 중 최소의 인덱스를 리턴, 만약 없으면 담능공간의 가장 끝 인덱스 + 1을 반환)
3. 찾은 lowerIdx, lowerIdx-1, lowerIdx +1 을 확인하면서 최소 합 특성값을 가진 두 용액을 업데이트한다.
[코드]
(1) 투 포인터 풀이
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll ;
int n ;
ll MAX = 1'000'000'000;
ll minTot = 2*MAX + 1 ; // 가장 작은 합 특성값 저장
vector<int> v(2) ; // 가장 작은 합 특성값을 만들어내는 두 용액 저장. pair로 해도 됨.
ll arr[100'001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n ;
for(int i = 0 ; i < n ; i++) cin >> arr[i];
int st = 0 ;
int en = n-1;
while(st < en ){
int sum = arr[st]+ arr[en];
if(abs(minTot) > abs(sum)) {minTot = sum ;
v[0] = arr[st];
v[1] = arr[en];
}
if(sum > 0) en--;
else if(sum < 0) st++;
else break;
}
cout << v[0]<<' '<< v[1] ;
}
(2) 이분 탐색 풀이
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll ;
int n ;
ll MAX = 1'000'000'000;
ll minTot = 2*MAX + 1 ;
vector<int> v(2) ;
ll arr[100'001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n ;
for(int i = 0 ; i < n ; i++) cin >> arr[i];
for(int i = 0 ; i < n ; i++){
int lowerIdx= lower_bound(arr,arr+n, -arr[i]) - arr ;
// lowerIndex의 왼쪽
if(lowerIdx != 0 && lowerIdx-1 != i && abs(arr[lowerIdx-1] + arr[i]) < abs(minTot)) {
minTot = arr[lowerIdx-1] + arr[i];
v[0] = arr[i];
v[1] = arr[lowerIdx-1] ;
}
// lowerIndex
if(lowerIdx < n && lowerIdx != i && abs(arr[lowerIdx] + arr[i]) < abs(minTot)) {
minTot = arr[lowerIdx] + arr[i];
v[0] = arr[i];
v[1] = arr[lowerIdx] ;
}
// lowerIndex의 오른쪽
if(lowerIdx < n-1 && lowerIdx+1 != i && abs(arr[lowerIdx+1] + arr[i]) < abs(minTot)) {
minTot = arr[lowerIdx+1] + arr[i];
v[0] = arr[i];
v[1] = arr[lowerIdx+1] ;
}
}
if(v[0] > v[1]) cout << v[1] <<' '<< v[0] ;
else cout << v[0] << ' '<< v[1];
}
[배울 점]
- 아무 생각이 들지 않을 때는 코드부터 생각하지말고, 문제의 핵심 조건을 고민하면서 어떤 식으로 접근할 지 고민을 먼저 하기.
- 테케가 틀렸을 때, 이분 탐색과 투 포인터는 경계 지점을 잘 확인할 것.
'알고리즘 > 백준' 카테고리의 다른 글
[백준/C++] 알고리즘 1405번 - 로봇 청소기 (0) | 2024.04.08 |
---|---|
[백준/C++] 알고리즘 13335번 - 트럭 (0) | 2024.04.08 |
[백준/C++] 알고리즘 2805번 - 나무 자르기 (0) | 2024.04.06 |
[백준/C++] 알고리즘 18869번 - 멀티버스 II (0) | 2024.04.06 |
[백준/C++] 알고리즘 3151번 - 합이 0 (0) | 2024.04.05 |