문제

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

상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다.

구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다.

지난 밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를 모두 정확하게 재고 돌아왔다. 구멍을 완벽하게 막을 수 있는 두 조각을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 구멍의 너비 x (1 ≤ x ≤ 20, x는 정수)가 주어진다. x의 단위는 센티미터이다.

다음 줄에는 물리 실험실에 있는 레고 조각의 수 n이 주어진다. (0 ≤ n ≤ 1000000)

다음 n개의 줄에는 레고 조각의 길이 ℓ이 주어진다. ℓ은 양의 정수이며, 단위는 나노미터이다. 블록의 길이는 10 센티미터 (100000000 나노미터)를 넘지 않는다.

출력

각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2)

정답이 여러 개인 경우에는 |ℓ1 - ℓ2|가 가장 큰 것을 출력한다.

예제

---

풀이

https://velog.io/@jxlhe46/C-scanf-cin이-데이터를-입력-받는-방법

몇개의 테스트 케이스가 들어오는지 알 수 없기 때문에 eof이 될 때까지 입력을 받아야 한다. 그 방법은 위의 포스트를 참고하자!

다음으로, 센티미터랑 나노미터의 차이를 알아보자!

1 cm = 10^(-2) m
1 nm = 10^(-9) m
→ nm에 10^7을 곱하면 cm가 된다.

1cm = 10000000 nm = 1 + 9999999 = 2 + 9999998

나노미터 단위의 조각 n (최대 100만)개 중에서 2개를 선택하여, 그 합이 x * 10^7 이 되도록 만들어보자. (x는 최대 20cm, l은 최대 10cm) 그리고 그러한 조합이 여러 개 나온다면, 두 값의 차이가 더 큰 것을 출력한다. ex) 9999999-1 > 9999998-2

투 포인터

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

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

	int x, n; // 구멍 너비 (cm), 조각의 개수
	while(cin >> x >> n){ // eof이 될 때까지 입력 받기 
		vector<int> v(n); // 각 조각의 길이 (nm)  
		for(int i = 0; i < n ; i++){ 
			cin >> v[i]; // 최대 10cm (10^8 -> 1억) 
		}

		sort(v.begin(), v.end()); // 오름차순 정렬 먼저 

		// 너비를 나노미터 단위로 변환 
		int width = x * pow(10, 7); 
		
		int left = 0;
		int right = n - 1;
		pair<bool, pair<int, int>> ans = {false, {0, 0}}; 
		while(left < right){ 
			int temp = v[left] + v[right];
			if(temp > width) 
				right--; // 합 줄이기 
			else if(temp < width) 
				left++; // 합 늘리기 
			else {
				ans = {true, {v[left], v[right]}}; 
				break; // 가장 먼저 발견된 쌍이 값의 차이가 최대임.  
			}
		}
	
		if(ans.first){ 
			pair<int, int> p = ans.second;
			cout << "yes " << p.first << " " << p.second << "\n";
		}else{
			cout << "danger\n"; 
		}
	}
	
	return 0;
}