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

 

11497번: 통나무 건너뛰기

 

 

정렬을 이용해서 그리디(Greedy)한 방법으로 풀 수 있는 전형적인 유형의 문제다.
그리디 알고리즘을 이용해야하는 문제들이 아이디어를 떠올리기만 하면 풀이가 간단해지는데 이 문제 역시 마찬가지다.
하지만 실버1 난이도의 문제인 만큼 핵심 아이디어를 찾기 까다롭지는 않은 편이다.

 

 

 

출처 - Baekjoon Online Judge

 

그림과 같이 통나무들을 원형으로 배치해 하나씩 건너 뛸 수 있게 한다는 컨셉이다.

문제에서 요구하는 것은 통나무들의 순서를 조정해서 바로 인접한 통나무의 높이 차이가 최소가 되어 뛰어다니기 쉽게 만드는 것이다.

각 통나무들의 높이가 주어졌을 때 인접한 통나무들의 높이차이 중 가장 큰 차이를 최소로 만들어 그 값을 출력하면 된다.

 

 

단 통나무들은 일직선으로 펼쳐진 것이 아니라 원형으로 양 끝이 연결된 형태를 고려해야 한다.

즉, 양 끝의 차이도 인접한 통나무의 높이차이에 포함된다.

 

 

---

 

 

문제의 포인트

 

아이디어 찾기

 

 

핵심 아이디어만 찾는다면 모든 조합의 경우의 수를 탐색하는 방식이 아니어도 해결 가능한 문제다.

어떤 입력이 주어지든 항상 한번에 최적의 조합을 만들 수 있다.

 

 

우선 통나무를 일직선 상에 배치할 때에 인접한 통나무 사이의 높이 차이를 최소화할 수 있는 방법을 생각해보자.

정렬을 통해 순차적으로 나열하기만 한다면 아주 쉽게 이 문제를 해결할 수 있다.

 

 

여기에 이 문제에서 추가한 요구사항은 단 하나다.

양 끝을 연결시킨 상태에서도 인접한 통나무 사이의 높이 차이가 최소가 되도록 만들라는 것이다.

일직선 상에 배치할 때와 같이 정렬시킨다면 양 끝의 높이 차이는 최대가 된다.

 

 

만약 가운데 놓을 통나무를 가장 높거나 낮게 배치하고 양 방향으로 점차 낮아지거나 높아지도록 배치해나가면 어떨까?

이렇게 하면 양 끝 통나무의 높이 차이를 가장 가깝게 만들 수 있을 것이다.

 

 

실제로 이렇게 배치하는 것을 시뮬레이션해보면 아래와 같은 순서로 놓으면 된다.

 

 

1. 통나무들을 높이 순서로 오름차순이나 내림차순으로 정렬시킨다.
2. 가장 크거나 작은 통나무를 가운데 배치한다.
3. 정렬된 순서로 가운데를 기준으로 하나씩 좌, 우에 배치한다.
4. 똑같은 방식으로 좌, 우 번갈아가며 배치한다.

 

 

위 과정을 그대로 프로그램으로 옮겨서 문제를 풀어가도 좋겠지만 항상 높이차이가 최소가 되는 배치 방식이므로 굳이 실제로 새로운 배열에 재배치 하지 않아도 어떤 순서로 높이 차이를 계산하면 되는지 알 수 있다.

 

 

 

 

그림처럼 정렬된 상태에서 [0] → [2], [2] → [4] 로 2칸씩 이동하는 방식으로 마지막 index까지 이동하고, 마지막 index에서는 방향을 바꿔 [3] → [1]과 같이 역시 기본적으로 2칸씩 이동으로 돌아오는 방법을 생각해보자.

단, 마지막 index에서 방향을 돌려 돌아올 때에는 이전에 어떤 통나무를 지나왔는지에 따라서 2칸이 아니라 1칸을 이동할 수 있다.

마지막에 시작점으로 돌아오는 순서에서도 마찬가지로 1칸을 이동할 수 있다.

 

 

이와 같이 정렬된 배열을 2칸 간격으로 참조하여 높이 차이를 계산하면 굳이 재배치하는 과정을 시뮬레이션 하지 않고 쉽게 답을 구할 수 있다.

즉, abs([0] - [2]), abs([2] - [4]), abs([4] - [3]), abs([3] - [1]), abs([1] - [0]) 을 구하고 이 중 가장 큰 값을 찾으면 된다.

 

 

하지만 여기에서도 추가적으로 불필요한 과정을 더 제거하면 훨씬 간단하게 답을 구할 수 있다.

바로 [3]과 [4], [0]과 [1] 과 같이 실제 정렬된 배열에서도 바로 인접한 1칸 사이의 값을 구하는 부분을 제거하는 것이다.

단순히 배열을 앞에서부터 순차적으로 2칸의 간격의 높이 값 차이만 계산하면 된다.

 

 

이것이 가능한 이유는 배열이 정렬되어있기 때문에 ([2] - [0]) > ([1] - [0]) 이 성립하기 때문이다.

이렇게 하면 정말 간단하게 문제를 해결할 수 있게된다.

 

 

---

 

 

전체 Code

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int T, N;

vector<int> L;

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

	int i, j, k, l;
	int curr, diff, max_diff;

	cin >> T;

	for (i = 0; i < T; i++) {
		L.clear();
		cin >> N;

		for (j = 0; j < N; j++) {
			cin >> l;
			L.push_back(l);
		}

		sort(L.begin(), L.end());
		max_diff = 0;

		for (k = 2; k < N; k++) {
			diff = abs(L[k] - L[k - 2]);
			if (diff > max_diff)
				max_diff = diff;
		}

		cout << max_diff << "\n";
	}

	return 0;
}