[백준 11497 - C++] 통나무 건너뛰기 : 그리디 알고리즘

www.acmicpc.net/problem/11497

11497번: 통나무 건너뛰기

문제

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

 

입력

입력은 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

 

풀이

 

이 문제를 푸는 방식으로 떠올린 아이디어는 위와 같다.

원형으로 배치되기 때문에 시작점, 끝점이 따로 없는 것이다.

따라서 하나의 통나무 양옆엔 가장 차이가 덜 나는 통나무를 두는 것이 좋다.

그러다 든 생각이 원을 반으로 뚝 짤라서 두줄로 나열한다고 생각하면 되겠다! 하는 생각이 들었다.

 

우선은 입력된 통나무의 길이를 오름차순으로 정렬해준다.

정렬된 배열: a0 ~ an-1으로 생각한다. (총 n개로 가정)

a0와 an-1은 두줄 모두의 양끝값으로 두고,

짝수번째 통나무들을 두는 곳과 홀수번째 통나무들을 두는 곳을 나눠서 max값을 구한다.

배열에 저장해야하나 생각했는데, 어차피 이전 높이와 비교만 하면 되므로 even_b, odd_b 변수만 가지고 구현하였다.

 

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

int main(void){
    int tc, n;
    int height[10000];
    int max = 0;
    int even_b, odd_b;  //이전꺼 저장
    int diff=0;
    
    scanf("%d", &tc);
    for(int j=0; j<tc; j++){
        max = 0;
        scanf("%d", &n);
        for(int i=0; i<n; i++){
            scanf("%d", &height[i]);
        }
        
        sort(height, height+n);
        even_b = height[0];
        odd_b = height[0];
      
        
        for(int i=1; i<n-1; i++){
            if(i%2 == 1){   //홀수
                diff = height[i] - odd_b;
                odd_b = height[i];
                if(max< diff)
                    max = diff;
            }
            else{
                diff = height[i] - even_b;
                even_b = height[i];
                if(max< diff)
                    max = diff;
            }

        }
        
        if(max < height[n-1] - odd_b)
            max = height[n-1] - odd_b;
        
        if(max < height[n-1] - even_b)
            max = height[n-1] - even_b;
        
        printf("%d\n", max);
    }
}