[C++] 백준 13018번: 특이한 수열 - Ad-hoc

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

13018번: 특이한 수열

 

입력으로 n, k가 주어지는데,

gcd(i, A[i])의 값이 1보다 큰 숫자가 정확히 k개가 되도록 수열을 만들어야한다.

 

이를 위해 처음 들었던 생각은 소수를 파악해야한다고 생각했다.

그런데 조금 손으로 끄적여보니, 사실 소수는 별로 중요하지 않다는 것을 알았다.

 

i번째 자연수와 i + 1번째 자연수의 gcd값 (gcd(i, i + 1))은 무조건 1이고 ,

A[i] = i (i > 1)인 경우 gcd(i, A[i])의 값은 곧 i가 될 것이므로

정확히 k개의 수만 본인 자리에 배치하고 나머지는 자신의 옆 인덱스의 값을 저장하면 된다.

 

쉽게 말해,

가령 N = 10, k = 3인 경우

A[10] = 10

A[9] = 9

A[8] = 8로 k개를 채워주고,

A[7] = 6, A[6] = 7

A[5] = 4, A[4] = 5 ...

이런식으로 수열을 완성해가면 

결국 원하는 수열을 만들 수 있게된다.

 

여기서 불가능한 경우가 존재하는데,

바로 n == k 인 경우이다.

gcd(1, 1) = 1이므로 1보다 큰 최대공약수는 존재할 수가 없다.

그러므로 n == k인 경우만 특이케이스로 분류하면 간단한 수열을 만들 수 있다.

 

#include <iostream>
#include <stack>
using namespace std;
int main(){
    int n, k; cin >> n >> k;
    stack<int>s;
    for(int i=n; i>n-k; i--) s.push(i);
    for(int i=n-k; i>1; i-=2){
        s.push(i-1);
        s.push(i);
    }
    if(n==k){
        cout << "Impossible";
        return 0;
    }
    if(s.size()!=n) s.push(1);
    while(!s.empty()){
        cout << s.top() << " ";
        s.pop();
    }
}