백준 1129 - 키

 

step 1

저희의 목표는 인접한 두 사람의 키 차이의 최댓값을 최소로 하려고 하는 것입니다. 우선 사전 순은 무시하고 최선을 다해 배치를 했을 때 키 차이의 최댓값을 구해 봅시다.

 

(가장 작은 사람) (많은 사람들) (가장 큰 사람) (또 많은 사람들) (가장 작은 사람)

 

을 원형으로 배치를 했다고 생각해 봅시다. 원형이라서 생각하기 어려우니

 

A: (가장 작은 사람) (많은 사람들) (가장 큰 사람)

B: (가장 큰 사람) (또 많은 사람들) (가장 작은 사람)

 

이렇게 두 줄로 쪼개봅시다. 아래쪽 줄을 뒤집으면

 

A: (가장 작은 사람) (많은 사람들) (가장 큰 사람)

B: (가장 작은 사람) (또 많은 사람들) (가장 큰 사람)

 

이 됩니다.

 

1. (많은 사람들)과 (또 많은 사람들)은 오름차순으로 정렬되어 있어야 합니다.

내려가는 부분이 있다면 해당하는 부분을 통채로 뒤집는 것이 더 이득입니다.

 

그럼

1. (가장 작은 사람)을 A와 B에 넣습니다.
2. 나머지 사람들을 작은 사람부터 A나 B에 넣습니다.
3. (가장 큰 사람)을 A와 B에 넣습니다.

이 과정을 통해 답을 구할 수 있습니다.

 

2. 사람들을 넣을 때 A와 B에 번갈아 가며 넣어야 합니다.

저희의 목표는 키 차이의 최댓값을 최소화 하는 것입니다. A와 B 모두 마지막에는 (가장 큰 사람)이 들어간다는 것을 생각하면 쉽게 유도할 수 있습니다.

 

이 두 규칙을 이용하면 배치가 하나로 정해지고 키 차이의 최댓값을 구할 수 있습니다.

step2

저희는 사람들을 다음과 같이 배치했습니다.

 

A: (가장 작은 사람) (많은 사람들) (가장 큰 사람)

B: (가장 작은 사람) (또 많은 사람들) (가장 큰 사람)

 

A를 순서대로 출력하고 B를 역순으로 출력해서 정답을 만들 것입니다.

입력이

7

1 3 5 6 7 9 10

이라고 가정해 봅시다. 위 방법에 따르면

 

A: 1 3 6 9 10

B: 1 5 7 10

이고 키 차이의 최댓값은 4입니다. 이 값을 X라고 합니다. 이제 사전순을 고려해 봅시다.

이전과 마찬가지로 A, B를 준비합니다. 

 

A: 1

B: 1

 

이제 3부터 순서대로 넣는데 A에 넣을 수 있으면 무조건 A에, 아니면 B에 넣을 것입니다. 구체적으로는 다음 사람과 B의 마지막 사람과의 키 차이가 X 이하면(지금 B에 들어가지 않아도 되면) A, 아니면 B에 넣습니다.

 

3, 5, 6, 7, 9, 10 순서로 넣습니다. 3 다음 사람인 5와 B의 마지막 사람인 1과의 차이는 4입니다. 지금 3을 B에 넣지 않아도 된다는 뜻이므로 A에 넣어줍니다.

 

A: 1 3

B: 1

 

5 차례 입니다. 다음 사람인 6이랑 B의 마지막 사람인 1의 차이는 5고 조건을 만족하지 못합니다. 5가 반드시 B에 들어가야 한다는 뜻이므로 B에 넣어줍니다.

 

A: 1 3

B: 1 5

 

6 차례 입니다. 다음 사람인 7이랑 B의 마지막 사람인 5와의 차이는 2고 조건을 만족합니다. 6을 A에 넣어줍니다.

 

A: 1 3 6

B: 1 5

 

7 차례 입니다. 다음 사람인 9랑 B의 마지막 사람인 5와의 차이는 4고 조건을 만족합니다. 7을 A에 넣어줍니다.

 

A: 1 3 6 7

B: 1 5

 

9 차례 입니다. 다음 사람인 10이랑 B의 마지막 사람인 5와의 차이는 5고 조건을 만족하지 못합니다. 9을 B에 넣어줍니다.

 

A: 1 3 6 7

B: 1 5 9

 

마지막 10은 양쪽에 넣어줍니다.

 

A: 1 3 6 7 10

B: 1 5 9 10

 

이제 A를 순서대로, B를 역순으로 출력하면 1 3 6 7 10 9 5가 됩니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int mapp[60][60];
int b[100],c[100];
int main() {
    int n, i,j, cost=0;
    scanf("%d", &n);
    for (i = 1;i <= n;i++) {
        scanf("%d", &b[i]);
    }
    sort(b + 1, b + n + 1);
    int s = 1;
    while (1) {
        int ps = s;
        if (s == n) break;
        s += 2;
        if (s > n) s = n;
        cost = max(cost, abs(b[s] - b[ps]));
    }
    if (n % 2 == 1) s = n - 1; else s = n - 2;
    cost = max(cost, abs(b[s] - b[n]));
    while (1) {
        int ps = s;
        if (s == 2) break;
        s -= 2;
        cost = max(cost, abs(b[s] - b[ps]));
    }
    cost = max(cost, abs(b[s] - b[1]));
    int x=2, y=1;
    printf("%d %d ", b[1],b[2]);
    c[1] = 1;
    c[2] = 1;
    for (i = 3;i <= n;i++) {
        if (b[i + 1] - b[y] > cost) y = i;
        else { printf("%d ", b[i]); x = i; c[i] = 1; }
    }
    for (i = n;i >= 1;i--) {
        if (c[i] == 0) printf("%d ", b[i]);
    }
    return 0;
}