11497_통나무 건너뛰기

1초 / 256MB

입력

입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다.

이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000), 둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다. (1 ≤ Li ≤ 100,000)

예제 입력 1 복사

3

7

13 10 12 11 10 11 12

5

2 4 5 7 9

8

6 6 6 6 6 6 6 6

예제 출력 1 복사

1

4

0

---

문제 접근

  이 문제를 읽고서 나는 꼭 배열을 정렬한 후 계산할 필요없이, 그냥 바로 답을 도출하면 되지 않을까?라는 생각을 떠올렸다. 통나무를 크기별로 정렬한후 앞에서 첫번째 통나무와 세번째 통나무만을 비교하는 것이다. 그렇게 하면 O(nlogn)의 시간복잡도로 문제를 풀 수 있지 않을까라는 생각이 떠올랐다.

  하지만, 이런식으로 풀게 될 경우, 2 5 6 7 8 같은 배열의 경우 3을 출력해야하지만 2를 출력하는 오류를 범하게 된다. 그러므로, 앞과 뒤에서 따로따로 max값을 찾아야 할 것 같ㄷ카.

 

문제 해결

  for문을 사용해 앞과 뒤에서 따로따로 반복문을 돌렸다. 그리고 반복문으로 못 찾는 예외적인 케이스들은 반복문 밖에다가 조건문으로 코딩했다.

 

// 통나무 건너뛰기
#include <iostream>
#include <algorithm>
#define MAX 10001
using namespace std;

int map[MAX];
int t, length, maxValue;

bool compare(const int a, const int b) {
	return a > b;
}

int main(void) {
	cin >> t;
	for(int i = 0; i < t; i++) {
		cin >> length;
		maxValue = 0;
		for(int j = 0; j < length; j++) {
			cin >> map[j];
		}
		sort(map, map + length, compare);
		if(length % 2 == 0) {
			int tmp;
			for(int j = 0; j <= length / 2; j++) {
				tmp = map[j] - map[j + 2];
				if(maxValue < tmp)
					maxValue = tmp;
			}
			for(int j = 0; j <= length / 2; j++) {
				tmp = map[length - (j + 3)] - map[length - (j + 1)];
				if(maxValue < tmp)
					maxValue = tmp;
			}
			tmp = map[0] - map[1];
			if(maxValue < tmp)
				maxValue = tmp;
			
			tmp = map[length - 2] - map[length - 1];
			if(maxValue < tmp)
				maxValue = tmp;
		}
		else {
			int tmp;
			for(int j = 0; j < length / 2; j++) {
				tmp = map[j] - map[j + 2];
				if(maxValue < tmp)
					maxValue = tmp;
			}
			for(int j = 0; j < length / 2; j++) {
				tmp = map[length - (j + 3)] - map[length - (j + 1)];
				if(maxValue < tmp)
					maxValue = tmp;
			}
			tmp = map[0] - map[1];
			if(maxValue < tmp)
				maxValue = tmp;
			
			tmp = map[length - 2] - map[length - 1];
			if(maxValue < tmp)
				maxValue = tmp;
		}
		cout << maxValue << endl;
	}
	return 0;
}