[백준 2470번 C/C++] 두 용액

 

[백준 2470번 C/C++] 두 용액

 

 

https://www.acmicpc.net/problem/2470

---

 

해결방안

 

투 포인터

 

---

 

처음 시도한 코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Solution
{
	int first, second, ave;
	Solution(int a, int b, int c)
	{
		first = a;
		second = b;
		ave = c;
	}
	bool operator<(const Solution& s){
		return ave < s.ave;
	}
};

int n;
vector<int> v; // 주어진 용액을 담는 배열
vector<Solution> result; // 첫번째 용액, 두번째 용액, 두 용액 섞었을때 pH 절대값을 담는 배열

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n);
	for(int i=0; i<n; i++){
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	int left = 0;
	int right = n - 1;
	while (left < right)
	{
		int sumSol = v[left] + v[right];

		if (sumSol == 0){
			cout << v[left] << " " << v[right] << "\n";
			return 0;
		}
		if (sumSol > 0) {
			right--;
		}
		if (sumSol < 0 && right < n - 1){
			result.push_back({ v[left], v[right + 1], abs(sumSol) });
			result.push_back({ v[left], v[right], abs(sumSol) });
			left++;
			right++;
		}		
	}

	sort(result.begin(), result.end());
	cout << result[0].first << " " << result[0].second << "\n";

	return 0;
}

시간초과

 

---

 

 

 

정답 코드

 

처음 시도한 코드를 수정한 정답 코드. Ver1.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Solution
{
	int first, second, ave;
	Solution(int a, int b, int c)
	{
		first = a;
		second = b;
		ave = c;
	}
	bool operator<(const Solution& s){
		return ave < s.ave;
	}
};

int n;
vector<int> v; // 주어진 용액을 담는 배열
vector<Solution> result; // 첫번째 용액, 두번째 용액, 두 용액 섞었을때 pH 절대값을 담는 배열

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n);
	for(int i=0; i<n; i++){
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	int left = 0;
	int right = n - 1;
	while (left < right)
	{
		int sumSol = v[left] + v[right];
        result.push_back({v[left], v[right], abs(sumSol)});

		if (sumSol == 0){
			cout << v[left] << " " << v[right] << "\n";
			return 0;
		}        

	    if (sumSol > 0) 
	        right--;
	    else  // sumSol < 0
	        left++;	
	}

	sort(result.begin(), result.end());
	cout << result[0].first << " " << result[0].second << "\n";

	return 0;
}

 

 

다른 풀이. Ver2.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> v; // 주어진 용액을 담는 배열
int resultSumSol = 2147000000;
int firstSol, secondSol;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n);
	for(int i=0; i<n; i++){
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	int left = 0;
	int right = n - 1;

	while (left < right)
	{
		int sumSol = v[left] + v[right];

		if (sumSol == 0){
			cout << v[left] << " " << v[right] << "\n";
			return 0;
		}

		if (abs(sumSol) < resultSumSol) {
			resultSumSol = abs(sumSol);
			firstSol = v[left];
			secondSol = v[right];
		}

		if (sumSol > 0) 
			right--;
        else 
			left++;
	}

	cout << firstSol << " " << secondSol << "\n";
	
	return 0;
}

 

 

 

 

---

 

고민한 부분

 

아래는 처음 시도해서 실패한 부분

resultSumSol의 초기값을 resultSumSol = abs(v[left] + v[right]);로 설정하였다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> v; // 주어진 용액을 담는 배열
int resultSumSol;
int firstSol, secondSol;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n);
	for(int i=0; i<n; i++){
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	int left = 0;
	int right = n - 1;
	resultSumSol = abs(v[left] + v[right]);

	while (left < right)
	{
		int sumSol = v[left] + v[right];

		if (sumSol == 0){
			cout << v[left] << " " << v[right] << "\n";
			return 0;
		}

		if (abs(sumSol) < resultSumSol) {
			resultSumSol = abs(sumSol);
			firstSol = v[left];
			secondSol = v[right];
		}

		if (sumSol > 0) 
			right--;		
		else // sumSol < 0
			left++;		
	}

	cout << firstSol << " " << secondSol << "\n";
	
	return 0;
}

 

첫 번째 코드에서는 resultSumSol을 용액들의 처음과 끝 값의 합으로 초기화했고, 아래의 두 번째 코드에서는 매우 큰 값을 이용하여 초기화했습니다.

첫 번째 코드에서 문제가 발생하는 이유는 

용액들이 모두 양수거나 모두 음수인 경우, 처음과 끝 값의 합은 실제 최소값이 아닐 수 있다. 따라서 이를 기준으로 비교하는 것은 올바르지 않다.
만약 입력된 용액들 중 어느 하나라도 절대값이 resultSumSol보다 크면, 그 용액을 사용한 조합은 절대로 선택되지 않게 된다. 즉, 첫 번째와 마지막 값의 합보다 큰 절대값을 가진 용액이 있는 경우, 그 용액을 포함하는 올바른 답을 찾을 수 없게 된다.
반면에 아래의 두 번째 코드에서는 resultSumSol를 매우 큰 값으로 초기화했다. 이렇게 함으로써 위에서 언급한 문제점들을 피할 수 있으며, 모든 가능한 조합들 중 최소값을 찾아낼 수 있다.

따라서 결과적으로 첫 번째 방식은 특정 입력에 대해 잘못된 결과를 출력할 가능성이 있으며, 두 번째 방식은 모든 입력에 대해 올바른 결과를 출력하게 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<int> v; // 주어진 용액을 담는 배열
int resultSumSol = 2147000000;
int firstSol, secondSol;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n);
	for(int i=0; i<n; i++){
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	int left = 0;
	int right = n - 1;

	while (left < right)
	{
		int sumSol = v[left] + v[right];

		if (sumSol == 0){
			cout << v[left] << " " << v[right] << "\n";
			return 0;
		}

		if (abs(sumSol) < resultSumSol) {
			resultSumSol = abs(sumSol);
			firstSol = v[left];
			secondSol = v[right];
		}

		if (sumSol > 0) 
			right--;
        else 
			left++;
	}

	cout << firstSol << " " << secondSol << "\n";
	
	return 0;
}