[C++]백준11497번 통나무 건너뛰기

오늘은 백준11497번 통나무 건너뛰기 문제를 풀어보도록 하자. 다양한 정렬방법이 있겠지만 데이터의 범위가 넓지 않아서 카운팅소트로 해결했다.

문제를 이해하는데 5분정도 걸린 것 같다. 최대 중 최소라는 말이 와닿지 않았다.

자세한건 접근법에서 !

문제는 다음과 같다.

                               [접근법]

  1. 우리는 최댓값 중에서 최솟값을 찾아야 한다. 따라서 어떤 모양이 나와야 값을 찾을 수 있는지 고민하던 중 삼각형 모양을 떠올렸다.
  
  2. 먼저 가장 큰 값을 넣어주고 그 기준으로 다음 큰 값들을 양 옆에 flag가 true면 push_front, false면 push_back을 해준다.

  3. 그리고 차이가 큰 값을 계속 갱신해주면서 가장 큰 값 중 작은 값을 찾으면 된다 ! :)

                                     [코드]
#include <iostream>
#include <algorithm>
#include <deque>
#include <cmath>
using namespace std;

int main() {
	int T,n,num;
	int arr[100001] = { 0, };
	bool flag = false;
	deque<int>dq;

	cin >> T;
	
	while (T--) {
		int result = -1;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> num;
			arr[num]++;
		}
		
		for (int i = 100000; i >= 1; i--) {
			while (1) {
				if (arr[i] > 0) {
					if (flag) {
						dq.push_front(i);
						flag = false;
					}
					else {
						dq.push_back(i);
						flag = true;
					}
					arr[i]--;
				}
				else {
					break;
				}
			}
		}
		for (int i = 0; i < n-1; i++) {
			result = max(abs(dq[i] - dq[i + 1]), result);
		}
		result = max(abs(dq[0] - dq[n-1]), result);
		cout << result << '\n';
		dq.clear();
	}
	return 0;
}