C++로 GCD 조건을 만족하는 처음 N개의 자연수 순열 찾기

문제 개요

두 정수 N과 K가 주어졌을 때, 처음 N개의 자연수로 이루어진 순열 P 중에서 GCD(P[i], i) > 1 조건을 만족하는 원소가 정확히 K개가 되는 경우를 찾아야 합니다. 여기서 조건은 1 ≤ i ≤ N 범위의 모든 인덱스에 대해 검사합니다.

예를 들어 N = 3, K = 1이라면 출력은 2, 1, 3이 됩니다. 이때 gcd(2, 1) = 1, gcd(1, 2) = 1, gcd(3, 3) = 3이므로 조건을 만족하는 원소는 마지막 하나뿐입니다.

접근 방법

이 문제는 간단한 아이디어로 해결할 수 있습니다.

마지막 K개의 원소는 원래 자리에 그대로 둡니다. 자기 자신과의 최대공약수는 항상 자기 자신이므로 gcd(x, x) = x > 1이 되어 조건을 만족합니다.
나머지 앞부분의 원소들은 한 칸씩 뒤로 밀어냅니다. 즉, i번째 원소를 (i + 1)번째 위치에 배치하고, (N - K)번째 원소는 첫 번째 위치로 옮깁니다.
이렇게 하면 인접한 수들이 서로 다른 위치에 놓이게 되는데, 연속된 두 자연수는 서로소이므로 gcd(x, x + 1) = 1이 항상 성립하여 앞부분에서는 조건을 만족하는 원소가 발생하지 않습니다.

C++ 구현 예제

#include<iostream>
using namespace std;

void findPermutation(int n, int k) {
    int permutation[n + 1];
    // 초기 상태: permutation[i] = i
    for (int i = 1; i <= n; i++)
        permutation[i] = i;
    // 앞부분 원소들을 한 칸씩 뒤로 이동
    for (int i = 1; i < n - k; i++)
        permutation[i + 1] = i;
    // (N-K)번째 원소를 첫 번째 위치에 배치
    permutation[1] = n - k;
    
    for (int i = 1; i <= n; i++)
        cout << permutation[i] << " ";
}

int main() {
    int n = 5, k = 2;
    cout << "The permutation is: ";
    findPermutation(n, k);
}

실행 결과

The permutation is: 3 1 2 4 5

동작 설명

N = 5, K = 2인 경우를 살펴보겠습니다.

초기 배열은 [1, 2, 3, 4, 5]입니다.
앞의 N - K = 3개 원소를 회전시키면 [3, 1, 2]가 되고, 마지막 2개 원소 [4, 5]는 그대로 유지됩니다.
결과 순열은 [3, 1, 2, 4, 5]입니다.

검증해 보면 gcd(3, 1) = 1, gcd(1, 2) = 1, gcd(2, 3) = 1로 앞 세 원소는 조건을 만족하지 않으며, gcd(4, 4) = 4, gcd(5, 5) = 5로 정확히 K = 2개의 원소만 조건을 충족합니다.

복잡도 분석

시간 복잡도: O(N) — 배열을 한 번씩 순회하므로 선형 시간에 처리됩니다.
공간 복잡도: O(N) — 크기 N + 1의 배열을 사용합니다.