BOJ 22952 - permutation making (S3)

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

22952번: permutation making

사용 알고리즘

constructive

 

풀이

N/2+1이 의미하는 것은, P에서 어떤 값을 가지는 정점이 2개씩 존재하도록 만들란 뜻이다.

어떤 값을 가지는 정점이 2개 존재한다는 것은, 어떤 값이 2개 나오도록 만들란 소리다. 어떤 i, j에서 P[i] = P[j]이려면   $$\sum _{k=1}^i{A}_k\equiv \sum _{k=1}^j{A}_k$$

가 mod N에서 성립하면 되며, 이는 $$\sum _{k=i+1}^j{A}_k$$ 가 N의 배수면 된다. 따라서

$$N/2,N/2-1,N/2-2,...,1,N,N-1,N-2,...,N/2+1$$

형태의 수열을 만들면 된다. (N은 홀수, N/2는 바닥함수를 생략한것이다.)

저게 가능한 이유는, 값 N을 기준으로 좌우에 대칭인 값을 더하면 N이 되기 때문이다.

N이 짝수이면 P[N] = N으로 정의하고 N에서 1을 빼면 된다.

예를 들어 N=5이면, 위 규칙에 따라 {2,1,5,4,3}이 되며, P = {2,3,3,2,0}이다.

금방 풀었지만 관찰 문제라서 생각이 안나면 굉장히 오래 걸릴 수도 있다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
typedef long long ll;
ll n;
ll a[101010];
void f(ll n){
    ll A = n;
    for(int i = n/2+1 ; i <= n ; i++)a[i] = A--;
    for(int i = 1 ; i <= n/2 ; i++)a[i] = A--;
}
int main(){
    fast;
    cin>>n;
    if(!(n&1)){
        a[n]=n;
        f(n-1);
        for(int i = 1 ; i <= n ; i++)cout<<a[i]<<" ";
    }
    else{
        f(n);
        for(int i = 1 ; i <= n ; i++)cout<<a[i]<<" ";
    }
}