42. UVa-11057 Exact Sum // given v, find (a,b) s.t. a+b=v

문제

 

<그림1: 문제 설명>

문제는 해석도 크게 어렵지 않다. 처음에 N이 주어지고 다음에 N개의 가격들이 주어진다. 그 다음 라인에 갖고있는 돈 M이 주어지는데, 갖고있는 돈 M으로 딱 맞춰서 살 수 있는 책 두 쌍의 가격 pair를 반환하는 것이다. 

스티븐 할림의 competitive algorithm책에서는 이진탐색풀이-input을 받고 정렬해서 각 원소 p[i]에 대해 M-p[i]를 이진탐색으로 찾기-를 제시했지만 이러면 시간복잡도가 nlgn+nlgn = 2nlgn이 나오는데, sorting 외의 nlgn작업은 예전에 풀었던 문제를 참고하면 n안에 수행할 수 있다. (UVa-10487의 아이디어 참고하기:https://hezma.tistory.com/56)

다음은 그 코드다.

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef vector<int> vi;

typedef pair<int, int> ii;
int main() {
	int N, M, temp,sum;
	/*--------------inputpart_start-------------*/
	while (cin >> N && !cin.eof()) {
		vi input;
		ii solution;
		for (int i = 0; i < N; i++) {
			cin >> temp;
			input.push_back(temp);
		}
		cin >> M;
	/*--------------inputpart_end-------------*/
		sort(input.begin(), input.end());
		vi::iterator frontit = input.begin();
		vi::iterator endit = --input.end();
		while (frontit!=endit) {
			sum = *frontit + *endit;
			if (sum < M) {
				++frontit;
			}
			else if (sum > M){
				--endit;
			}
			else { //sum == M
				solution = make_pair(*frontit, *endit);
				++frontit;
			}
		}
		cout << "Peter should buy books whose prices are " << solution.first << " and " << solution.second << "." <<endl<<endl;


	}


	return 0;
}