【백준】- 20921. 그렇고 그런 사이

문제

https://www.acmicpc.net/problem/20921

20921번: 그렇고 그런 사이

풀이

$N$ 이 최대 $4\;242$ 이기 때문에, $O(N^2)$ 와 $O(N)$ 의 시간복잡도의 풀이 모두 사용할 수 있습니다. 저는 두 방법 모두 설명해 보고자 합니다. 여러분은 어느 방식으로 푸셨나요?

$O(N^2)$ 풀이

인접한 번호를 서로 교환해 보기

여기 사람들의 번호가 일렬로 나열되어 있습니다. 이 상태에서, 두 인접한 번호(오른쪽 번호가 더 큰)를 골라 서로의 위치를 바꾸었다고 가정해 볼게요. 과연 그렇고 그런 사이의 개수는 어떻게 달라질까요?

• 교환한 두 수를 기준으로 왼쪽에 있는 수들(붉은색) - 개수가 변하지 않습니다. 개수가 변하려면, 새롭게 교환되는 수가 자신의 왼쪽으로 와야 대소 관계가 바뀌기 때문입니다. 하지만 위 상황에서는 두 인접한 수가 교환되더라도 그 수들은 교환 전과 교환 후 모두 자신보다 오른쪽에 수가 있기 때문에 변하는 것이 없습니다.
• 교환한 두 수를 기준으로 오른쪽에 있는 수들(푸른색) - 붉은색 수들과 마찬가지로 개수가 변하지 않습니다. 두 인접한 수가 교환되더라도, 자신의 입장에서는 그 수들이 자신의 왼쪽에 있는 것은 변함없기 때문입니다.
• 교환되는 두 수들(노란색) - 개수가 $1$ 개 증가합니다! 두 수를 교환하면 대소 관계도 바뀌니까요.

결론적으로, 임의의 인접한 두 수 $A$, $B$ $(A < B)$ 를 선택해 서로 교환하면 정확히 그렇고 그런 사이의 개수가 $1$ 개 증가합니다!

아이디어를 써먹어 봅시다

위의 아이디어를 이제 본격적으로 써먹어 봅시다!

우선, 사람들의 번호를 먼저 오름차순으로 나열해 봅니다. $N = 4$ 라면, $[1, 2, 3, 4]$ 와 같이요. 이렇게 하면 어떠한 두 수를 골라도 오른쪽 수가 항상 더 크므로, 그렇고 그런 사이의 개수는 $0$ 이 됩니다.

이 상태에서, 이제 인접한 두 수 $A$, $B$ $(A < B)$ 를 선택해 교환할 때마다 그렇고 그런 사이의 개수를 $1$ 개씩 증가시킬 수 있습니다. 여기서는 인접한 두 수를 선택할 때 가장 오른쪽에 있는 수들부터 차례로 선택해 봅시다. 마치 버블 정렬을 거꾸로 돌리듯이요. 아래의 그림을 참고해 주세요!

이렇게 하면, 주어진 입력 범위 내에서 어떤 $K$ 값이 들어오든 조건을 만족하는 구성을 만들 수 있습니다. $K$ 번 인접한 수를 교환하는 작업을 수행하면 되거든요. 수의 교환을 최대한으로 했을 경우에는 번호가 내림차순이 되고, 교환은 총 $\frac{N(N-1)}{2}$ 회 일어나게 됩니다.

$O(N)$ 풀이

위의 방법대로 문제를 풀어도 충분히 통과할 수 있지만, 더 효율적인 방법이 있습니다.

수들을 내림차순으로 적어본다면?

$N = 6$ 이고, 아직 아무 번호도 정해지지 않았다고 가정해 봅시다.

이 상태에서, 첫 번째 번호로 $6$ 을 적어보겠습니다. 그러면, 첫 번째 번호와 다른 번호를 짝을 맺어 만들 수 있는 그렇고 그런 사이는 $5$ 개가 됩니다. 뒤에 나올 수들이 어떤 순서로 나올 지는 아직 정해지지 않았지만, 어쨌든 $1$ 부터 $5$ 까지의 번호가 각각 한 번씩 나올 것이고, 이 수들은 순서에 관계없이 첫 번째 번호인 $6$ 보다 작으면서 오른쪽에 있기 때문입니다.

두 번째 번호로 $4$ 를 적었을 때에도 마찬가지입니다. 어쨌든 $1$ 부터 $3$ 까지의 번호가 각각 한 번씩, $4$ 의 오른쪽에 나오겠죠? 이렇게 하면 두 번째 번호와 오른쪽에 있는 수를 이용해 만들 수 있는 그렇고 그런 사이는 $3$ 개가 됩니다.

오른쪽에 있는 수하고만 짝을 짓는 이유는, 왼쪽에 있는 수와 짝을 지을 경우 이전 번호에서 짝을 지은 경우와 중복되기 때문입니다.

내림차순으로 수를 적지 않을 경우에는 위의 방식이 성립하지 않습니다. 세 번째 번호로는 $5$ 를 적었는데, $5$ 와 오른쪽에 있는 번호들을 짝지었을 때 만들 수 있는 그렇고 그런 사이는 $4$ 개일까요?

아닙니다. $1$ 부터 $4$ 까지의 번호가 모두 $5$ 의 오른쪽에 있어야 하는데, $5$ 보다 작은 수인 $4$ 를 이미 적었기 때문입니다. 수들을 내림차순으로 적는다는 것은, 자신의 수보다 작은 수들이 항상 오른쪽에 있음이 보장된다는 의미입니다.

 

결론적으로, 수들을 모두 내림차순으로 적어나간다는 조건을 지킨다면, 수 $X$ 를 적었을 때 만들 수 있는 그렇고 그런 사이의 개수는 $X - 1$ 개가 늘어납니다.

아이디어를 써먹어 봅시다

위의 아이디어를 이용해, 이렇게 수를 적어나가면 어떨까요?

1. 가장 큰 수부터, $1$ 씩 줄어들게 하면서 수를 적습니다. 수를 적을 때마다, 만든 그렇고 그런 사이를 $K$ 에서 뺍니다. 수 $X$ 를 적었다면, $X - 1$ 개를 빼면 됩니다.
2. 만약 남은 수 $K$ 가 얼마 남지 않아 $X - 1$ 보다 작은 상황이 되었다면, $K$ 의 남는 수가 $0$ 이 되도록 적절히 더 작은 수를 적습니다.
3. 이제 $K$ 가 $0$ 이 되어 필요한 그렇고 그런 사이의 개수를 채운 상황입니다. 이제부터는 아직 사용하지 않은 모든 수들을 오름차순으로 적습니다. 이렇게 하면 더 이상 그렇고 그런 사이가 만들어지지 않습니다.

$N = 6$, $K = 11$ 를 예로 들어볼까요?

1. 첫 번째 수로 $6$ 을 적었습니다. 그렇고 그런 사이는 $5$ 개가 생기므로, $K = 6$ 이 남게 됩니다.
2. 두 번째 수로 $5$ 를 적었습니다. 그렇고 그런 사이는 $4$ 개가 생기므로, $K = 2$ 이 남게 됩니다.
3. 세 번째 수로 $4$ 를 적어야 하는데, 그렇게 되면 그렇고 그런 사이가 $3$ 개가 생겨 $K = -1$ 이 됩니다. 이 경우 문제에서 요구한 것보다 더 많은 그렇고 그런 사이를 만든 것이 됩니다. 우리가 더 만들어야 하는 그렇고 그런 사이는 $2$ 개이므로, $2 + 1 = 3$ 을 세 번째 수로 적어줍시다.
4. 이제 더 이상 그렇고 그런 사이를 만들어서는 안 되므로, 아직 사용하지 않은 번호인 $1$, $2$, $4$ 는 오름차순으로 적어 줍니다.

이렇게 하면, 시간복잡도 $O(N)$ 에 문제를 해결할 수 있게 됩니다!

코드

• $O(N^2)$ 풀이 (C++)

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

int numbers[4243];
int N, K;

void fill_numbers() {
    for (int i = 1; i <= N; i++) {
        numbers[i] = i;
    }
}

void make_soso_relationship() {
    for (int i = 1; i <= N - 1; i++) {
        for (int j = N - 1; j >= i; j--) {
            if (K <= 0) return;

            swap(numbers[j], numbers[j + 1]);
            K -= 1;
        }
    }
}

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

    cin >> N >> K;

    fill_numbers();
    make_soso_relationship();

    for (int i = 1; i <= N; i++) {
        cout << numbers[i] << ' ';
    }
}

• $O(N)$ 풀이 (C++)

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

int is_used[4243];

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

    int N, K;
    cin >> N >> K;

    for (int i = N; i >= 1; i--) {
        if (K == 0) break;

        int matched = min(K, i - 1);
        K -= matched;
        is_used[matched + 1] = true;

        cout << matched + 1 << ' ';
    }

    for (int i = 1; i <= N; i++) {
        if (!is_used[i]) cout << i << ' ';
    }
}

비슷한 문제

• 17505번 - 링고와 순열

이 문제와 사실상 동일한 문제입니다. 대신, $N$ 값이 최대 $314\;159$ 입니다. 만약 $O(N^2)$ 으로 이 문제를 푸셨다면 이번에는 $O(N)$ 으로 이 문제를 풀어보시는 것은 어떨까요?