[백준 13018] 특이한 수열

문제

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

13018번: 특이한 수열

 

풀이

아래와 같이 몇 가지를 관찰하여 해결할 수 있습니다.

 

1. 1 ~ n까지의 수를 순서대로 둘 때, 1을 제외한 모든 수는 gcd(i, A[i]) > 1을 만족합니다. 따라서 주어진 조건을 만족하는 최대 k값은 n - 1이므로 n == k인 경우 불가능합니다. 

 

2. gcd(i, A[i]) > 1을 k개의 수가 만족한다는 것은 gcd(i, A[i]) > 1을 n - k개 만족하지 않는다는 것과 같습니다. 1에서 순서대로 놓은 수들은 1을 제외하고 모두 gcd(i, A[i]) > 1을 만족하므로 편의를 위해 k에 n - k를 넣어 만족하지 않는 k개의 수들의 순서를 바꾸면 됩니다.

 

3. gcd(1, A[i])가 1인 것과 gcd(A[i], A[i] + 1)가 1인것을 이용하면 k개의 만족하지 않는 수의 순서를 만들 수 있습니다.

     

     (1) k가 홀수일 때  = 2부터 k가 0이 될 때까지 두 수의 순서를 뒤바꿔서 출력

     (2) k가 짝수일 때  = 1부터 k가 0이 될 때 까지 두 수의 순서를 뒤바꿔서 출력

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, k, s;

int main(){
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> k;
	if (n == k){
		cout <<"Impossible";
		return 0;
	}
	k = n - k, s = 1;
	if (k % 2) cout << 1<<" ", k--, s = 2;
	for (int i = s; i<= n; i++)
		if (k) cout << i + 1 <<" " << i<<" ", k -= 2, i++;
		else cout <<i<<" ";
}