문제 개요
두 정수 N과 K가 주어졌을 때, [1부터 N] 범위의 정수들로 구성된 순열 P 중에서 gcd(P[i], i) > 1을 만족하는 인덱스(1-based indexing)의 개수가 정확히 K가 되는 순열을 찾는 것이 목표입니다.
예를 들어 N = 4, K = 3이라면 정답은 [1, 2, 3, 4]입니다. 각 위치별로 gcd(1, 1) = 1, gcd(2, 2) = 2, gcd(3, 3) = 3, gcd(4, 4) = 4이므로, 최대공약수가 1보다 큰 인덱스는 2번, 3번, 4번으로 총 3개(K = 3)이기 때문입니다.
핵심 관찰
문제를 자세히 살펴보면 다음과 같은 중요한 성질을 발견할 수 있습니다.
- gcd(i, i+1) = 1 : 연속한 두 정수는 항상 서로소입니다.
- gcd(1, i) = 1 : 1과 임의의 정수의 최대공약수는 항상 1입니다.
- gcd(i, i) = i : 같은 수끼리의 최대공약수는 그 수 자신입니다.
임의의 수와 1의 GCD는 항상 1이므로, 조건을 만족하는 인덱스 개수 K의 최댓값은 N - 1입니다. 실제로 P[i] = i인 항등 순열(identity permutation)을 사용하면 gcd(P[i], i) > 1인 인덱스는 1번 위치를 제외한 나머지 N - 1개가 됩니다.
교환 전략
항등 순열에서 출발하여 원하는 K에 맞춰 조건을 만족하는 인덱스 수를 조정할 수 있습니다.
- 1을 제외한 연속된 두 원소를 교환하면 조건을 만족하는 인덱스 수가 정확히 2씩 감소합니다.
- 원소 1과 다른 원소를 교환하면 조건을 만족하는 인덱스 수가 정확히 1 감소합니다.
이 두 가지 연산을 적절히 조합하면 가능한 모든 K 값에 대해 답을 구성할 수 있습니다. 단, k ≥ n인 경우 또는 n이 짝수이면서 k = 0인 경우에는 유효한 순열이 존재하지 않으므로 -1을 출력합니다.
C++ 구현 코드
#include<iostream>
using namespace std;
void findPermutation(int n, int k) {
if (k >= n || (n % 2 == 0 && k == 0)) {
cout << -1;
return;
}
int P[n + 1];
for (int i = 1; i <= n; i++)
P[i] = i;
int count = n - 1;
for (int i = 2; i < n; i+=2) {
if (count - 1 > k) {
swap(P[i], P[i + 1]);
count -= 2;
} else if (count - 1 == k) {
swap(P[1], P[i]);
count--;
} else
break;
}
for (int i = 1; i <= n; i++)
cout << P[i] << " ";
}
int main() {
int n = 5, k = 3;
cout << "Permutation is: ";
findPermutation(n, k);
}실행 결과
Permutation is: 2 1 3 4 5
N = 5, K = 3인 경우, 알고리즘은 먼저 항등 순열 [1, 2, 3, 4, 5](조건 만족 인덱스 4개)에서 시작하여 첫 번째 교환으로 count를 3으로 만든 뒤 조건을 충족하므로 [2, 1, 3, 4, 5]를 출력합니다. 실제로 이 순열에서 gcd(2, 1) = 1, gcd(1, 2) = 1, gcd(3, 3) = 3, gcd(4, 4) = 4, gcd(5, 5) = 5이므로 조건을 만족하는 인덱스는 정확히 3개입니다.
정리
이 문제는 항등 순열의 특성과 인접 원소 교환이 GCD 조건에 미치는 영향을 이해하면 O(N) 시간 복잡도로 해결할 수 있습니다. 불가능한 경우(N보다 큰 K, 짝수 N에서 K = 0)를 먼저 걸러내는 것이 구현의 핵심 포인트입니다.