[백준 C++] 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이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

 

 

---

문제 풀이 전략

 

기획

 

 무척이나 간단하다. 먼저 통나무의 길이순으로 나열한후, 각 통나무의 길이를 a1부터 시작하여 an까지 존재하는 배열로 나타낸다(지금 여기서는 설명을 위해, 통나무의 개수가 홀수라는 가정하에 글을 작성한다). 이후 다시 a1, a3, a5, ..., an의 순서로 새로운 배열(또는 벡터)에 집어넣고, 그 뒤로 an-1, an-3, ..., a4, a2 순으로 집어넣는다.

 

 가령 1, 5, 3, 4, 2로 이루어진 배열이 있다 가정해보자. 그 후 이것을 1 2 3 4 5로 나열한다. 그리고 난 뒤 이 배열의 {첫 번째, 세 번째, 다섯 번째, 네 번째, 두 번째} 원소 순으로 새로운 배열을 만든다. 그렇다면 1 3 5 4 2 순이 될 것이다. 이것이 바로 남규가 찾는 정답이다.

 

 짝수인 경우는 조금 다르다. a1, a3, ..., an-3, an-1, an, an-2, an-4, ..., a4, a2와 같은 순서로 정답 배열이 만들어진다.

 

 

주의사항

 

 주어진 통나무의 개수가 짝수인지 홀수인지에 따라서, 처리가 조금 달라진다. 이 부분만 유의해서 문제를 풀면 별탈없이 해결 가능할 것이다.

---

소스 코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solveProblem();
void solveTestCase();

int arr[10000];
int t, n;

int main()
{
    solveProblem();

    return 0;
}

void solveProblem()
{
    scanf("%d", &t);

    for(int i = 0; i < t; i++)
    {
        scanf("%d", &n);

        for(int j = 0; j < n; j++)
            scanf("%d", &arr[j]);

        solveTestCase();
    }
}

void solveTestCase()
{
    sort(arr, arr + n);

    vector<int> ansArr;

    for(int i = 0; i < n; i += 2)
        ansArr.push_back(arr[i]);

    if(n % 2 == 1)
        for(int i = n - 2; i >= 0; i -= 2)
            ansArr.push_back(arr[i]);
    else
        for(int i = n - 1; i >= 0; i -= 2)
            ansArr.push_back(arr[i]);

    int ans = ansArr[n-1] - ansArr[0];

    for(int i = 0; i < n - 1; i++)
    {
        int tmp = abs(ansArr[i] - ansArr[i + 1]);

        if(tmp > ans)
            ans = tmp;
    }

    printf("%d\n", ans);
}

---

테스트 케이스

 

[예제 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
4
0



[예제 2]
입력:
3
6
1 1 2 2 3 3
5
1 2 2 3 3
7
1 100 29 188 300 192 213

출력:
1
1
159