[백준/C++] 3649 로봇 프로젝트

 

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

 

코드

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

#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);

int main() {
    FASTIO;
	int x, n;
	while (cin >> x >> n) {
		x *= 10000000;

		vector<int> v(n);
		for (int i = 0; i < n; i++) cin >> v[i];

		sort(v.begin(), v.end());

		int s = 0, e = n - 1, sum;
		bool find = false;
		while (s < e && !find) {
			sum = v[s] + v[e];
			if (sum == x) {
				cout << "yes " << v[s] << " " << v[e] << "\n";
				find = true;
			} 

			if (sum > x) e--;
			else s++;
		}
		if (!find) cout << "danger\n";
	}
	return 0;
}

설명

레고 두 개의 합 = 구멍의 너비를 충족하는 경우를 찾으면 된다. 그리고 해당 경우가 여러 개일 경우 두 수 간 격차가 가장 큰 경우로 출력하면 되니 레고의 길이들을 오름차순 정렬한 후 투포인터를 사용했다.

 

느낀 점

처음에 문제를 읽고 바로 예제 입력을 봤는데 구멍의 너비와 레고 조각의 길이가 같은 단위인 줄 알고 당황했었다... 입력을 읽고 나서 제대로 파악해서 풀었다. 투 포인터를 이용해서 풀었다!