# [Gold IV] 특이한 수열 #### [문제 링크](https://www.acmicpc.net/problem/13018) ## 문제 설명 <p>이 문제는 특이한 수열 A를 찾는 문제이다. 특이한 수열의 성질은 다음과 같다.</p> <ul> <li>수열 A의 길이는 n</li> <li>1이상 n이하의 정수가 빠짐없이 모두 등장해야 하며, 각 수는 한번만 등장해야함</li> <li>1 ≤ i ≤ n 인 i에 대해 gcd(i, A[i]) > 1 을 만족하는 i가 정확히 k개여야함</li> </ul> <p>n, k 가 주어졌을 때, 특이한 수열을 아무거나 하나 구해보자.</p> ## 입력 <p>첫째 줄에 n, k (1 ≤ n ≤ 10⁵, 0 ≤ k ≤ n)가 주어진다.</p> ## 출력 <p>첫째 줄에 문제의 조건을 만족하는 특이한 수열 A를 출력한다. 답이 여러 가지가 있다면 그 중 아무거나 출력해도 된다. 만약 조건을 만족하는 특이한 수열이 없다면 "Impossible" 을 출력한다.</p> ## 풀이 #### 인접한 정수끼리의 gcd는 1이라는 성질을 이용해서 인접한 정수끼리 스왑하여 줄이고 늘리면 됩니다. 따라서 n==k인 경우를 제외하고 모든 경우를 만들 수 있습니다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; if(n==k) { cout << "Impossible"; } else { int cnt = n-1-k, outputCnt=1; if(cnt%2==1) cout << n << ' '; // 홀수번 바뀌어야 하는 경우 (1과 스왑해야함) else cout << "1 "; for(int i=2;i<n;i+=2) { if(cnt>=2) { // 스왑 cout << i+1 << ' ' << i << ' '; cnt-=2; outputCnt+=2; } else { if(i+1==n) { cout << i << ' '; outputCnt++; } else { cout << i << ' ' << i+1 << ' '; outputCnt+=2; } } } if(outputCnt!=n) { if(cnt%2==1) cout << 1; else cout << n; } } } ```