[BOJ/2467] 용액

www.acmicpc.net/problem/2467

2467번: 용액

github.com/jokj624/PS/blob/master/1000-5000/2467.cpp

jokj624/PS

 한줄 후기 : 그냥 문제가 뭔가 KOI 같았음

 

용액 문제가 뭔가 KOI 스러워서 봤는데 진짜였음 ;; ㅎㄷㄷ

첨 보고 투포인터나 이분탐색 같애~ 이러고 끄고 다른날 (오늘) 풀었는데

투포인터로 풀었다

첨 생각한 방법은

//WA
//BOJ 2467 용액
#include <iostream>
#include <vector>
#include <algorithm>
#define INF 9876543210
using namespace std;
typedef long long ll;
int arr[101010];
int main(){
	int N;
	cin >> N;
	for(int i=0; i<N; i++){
		scanf("%d", &arr[i]);
	}
	int l = 0, r = N-1, ansL=0, ansR=1;
	ll ans = INF;
	while(r >= 0 && l < N ){
		if(l == r)	l++;
		ll sum;
		sum = arr[l]+arr[r];
		if(sum == 0){
			ansL = l;	ansR = r;
			break;
		}
		if(ans > abs(sum)){
			ans = abs(sum);
			ansL = l;
			ansR = r;
		}
		else if(sum < 0){
			l++;	r--;
		}
		else{
			r--; 	l++;
		}
	}
	if(ansL < ansR)		cout << arr[ansL] << " " << arr[ansR];
	else	cout << arr[ansR] << " " << arr[ansL];
	return 0;
}

l = 시작 r=끝 으로 두고 sum (두개 용액을 더한 값)이 0보다 작거나 클때를 찾아서 l을 늘리고 r을 빼줬는데 

생각해보니 저렇게 하면 if문 비교를 할 필요가 없는 코드였다. 아직 한참 멀었음 ㅋㅋ

그래서 엄청나게 틀리고 

//AC
//BOJ 2467 용액
#include <iostream>
#include <vector>
#include <algorithm>
#define INF 9876543210
using namespace std;
typedef long long ll;
int arr[101010];
int main(){
	int N;
	cin >> N;
	for(int i=0; i<N; i++){
		scanf("%d", &arr[i]);
	}
	int l = 0, r = N-1, ansL=0, ansR=1;
	ll ans = INF;
	while(l < r){
		if(l == r)	l++;
		ll sum;
		sum = arr[l]+arr[r];
		if(sum == 0){
			ansL = l;	ansR = r;
			break;
		}
		if(ans > abs(sum)){
			ans = abs(sum);
			ansL = l;
			ansR = r;
		}
		else if(sum < 0){
			l++;
		}
		else{
			r--; 
		}
	}
	if(ansL < ansR)		cout << arr[ansL] << " " << arr[ansR];
	else	cout << arr[ansR] << " " << arr[ansL];
	return 0;
}

고쳐서 맞았다.

sum < 0 이면 현재 값이 음수인거니 (정렬된 수열이므로) l을 늘려준다. 만약 sum > 0이면 양수이니 r을 하나 빼주면 된다.

이런 식으로 비교했을 때, 합이 0 이 나오면 바로 break하면 되고, 그게 아니라면 ans(현재까지 중에 가장 0과 비슷한 합의 값) 과 비교해줘서 더 작은 값으로 갱신해준다.

마지막 출력은 오름차순으로 해야하니 저렇게 비교해 출력한건데, 사실 l<r이라는 while문 조건 때문에 크게 필요 없을 것 같다. 이분 탐색으로도 풀 수 있다고 한다.