[코드포스 - 1705A] Mark the Photographer

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
#define HMAX 1005
int h[HMAX];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int T; cin >> T;
	while(T--)
	{
		//1. get input
		int N, X; cin >> N >> X;
		int NN = 2 * N;
		for (int i = 0; i < NN; ++i)
		{
			cin >> h[i];
		}

		//2. sort
		sort(h, h + NN, less<int>());

		//3. calculate
		bool bIsCan = true;
		for (int i = 0; i < N; ++i)
		{
			//3-b. 요구한 최소 차이보다 작으면
			if (h[i + N] - h[i] < X)
			{
				bIsCan = false;
				break;
			}
		}

		cout << (string)(bIsCan? "YES\n" : "NO\n");
	}
	return 0;
}

---

||사고 과정

영어 번역하는데만 15분이 걸렸다ㅋㅋㅋㅋㅋ ㄷㄷ

쭉 정렬하고 앞줄[i]와 뒷줄[i]를 검사하면서 답을 도출하는 그리디 형식이라고 생각이 들었다.

 

그래서 앞줄과 뒷줄의 차이가 x이상이어야 하는 조건이라 오름차순으로 쭉 정렬하고

i와 i + n 인덱스를 비교하면  앞줄[i]와 뒷줄[i]를 검사하는게 되어 이렇게 검사를 하고

중간에 끊기 위해 bool추가하고 답을 출력했다.

---

||사용 기법

• Greedy

---

||풀면서 느낀 것

• 영어 해석을 좀 더 빨리 해봐야겠다.

시간이 걸리더라도 이번처럼 일단 나 혼자 해석해보고 하는게 중요한것 같다.

• 이상,이하,초과,미만

영어에서 이런 범위적인 실수가 조금 나오는데 확실히하고 넘어가야겠다.

---

||새로 알게 된것

• std::vector end( )

이번에 정확히 알았다.

마지막 원소의 다음번째 주소로 아무것도 가르키지 않는다..!

 

이걸 왜 사용하냐면 표준 라이브러리의 함수에 범위를 넣으면 마지막 범위는 참조하지 않기 때문에

마지막 원소까지 참조하게 하려고 사용하던 것이였다!

 

그 예로 sort같은 함수가 있겠다.

sort를 배열로 사용한다면 예시는 이렇다.

int a[5] {1,2,3,4,5};
//마지막 주소인 a + 4의 다음인 a + 5를 end자리에 넣어준다.
sort(a, a + 5);

https://cplusplus.com/reference/algorithm/sort/

https://cplusplus.com/reference/vector/vector/end/