C++에서 주어진 식의 결과가 정확히 2K가 되도록 2N개 자연수의 순열 찾기

두 정수 N과 K가 주어졌을 때, 1부터 2N까지의 자연수로 이루어진 순열 중 아래 식을 만족하는 것을 찾는 문제입니다.

$$\displaystyle\sum\limits_{i=1}^N\lvert A_{2i-1}-A_{2i}\rvert-\Bigl\lvert \displaystyle\sum\limits_{i=1}^N (A_{2i-1}-A_{2i}) \Bigr\rvert=2K$$

단, K의 값은 항상 N보다 작거나 같아야 한다는 조건이 붙습니다.

예제

N = 4, K = 1인 경우를 살펴보겠습니다. 이때 출력은 2 1 3 4이며, 주어진 식의 계산 결과는 다음과 같습니다.

(|2 − 1| + |3 − 4|) − (|(2 − 1) + (3 − 4)|) = 2 − 0 = 2

접근 방법

핵심 아이디어는 매우 간단합니다. 먼저 1, 2, 3, 4, 5, 6, …처럼 정렬된 수열을 떠올려 봅시다. 이 상태에서 임의의 인접한 두 위치 2i − 1과 2i에 있는 원소를 서로 맞바꾸면, 위 식의 결과값이 정확히 2씩 증가합니다.

따라서 정렬된 수열에서 앞쪽 K개의 쌍만 순서를 뒤집어 주면, 결과값이 정확히 2K가 되는 순열을 손쉽게 만들 수 있습니다.

알고리즘 단계

1. i번째 쌍 (2i − 1, 2i)에 대해, i ≤ K이면 두 수의 순서를 뒤집어 2i, 2i − 1 순으로 출력합니다.
2. i > K이면 원래 순서 그대로 2i − 1, 2i를 출력합니다.

이 방식은 수열을 한 번만 순회하면 되므로 시간 복잡도는 O(N)입니다.

C++ 구현

#include<iostream>
using namespace std;

void showPermutations(int n, int k) {
    for (int i = 1; i <= n; i++) {
        int a = 2 * i - 1;
        int b = 2 * i;
        if (i <= k)
            cout << b << " " << a << " ";
        else
            cout << a << " " << b << " ";
    }
}

int main() {
    int n = 4, k = 2;
    showPermutations(n, k);
    return 0;
}

출력 결과

2 1 4 3 5 6 7 8

위 예제에서는 N = 4, K = 2이므로 앞의 두 쌍만 서로 뒤바뀌어 2 1, 4 3으로 출력되고, 나머지 쌍은 원래 순서인 5 6, 7 8 그대로 출력됩니다.