[C++] [CSES] Permutations (Introductory Problems)

CSES 다섯번째 문제입니다.

beautiful 한 순열을 프린트하는 문제입니다. beautiful하다는 것은 모든 인접한 숫자들이 2 이상 차이나는 순열입니다.

예를 들면 3 1 4 2 과 같이 바로 옆 숫자들과 자신의 차이가 모두 2 이상 차이납니다.

하지만 2 4 3 1 순열에서는 4와 3의 차이가 1이기 때문에 beautiful하지 않은 순열입니다.

 

Task

 

A permutation of integers 1,2,…,n is called beautiful if there are no adjacent elements whose difference is 11.
Given n, construct a beautiful permutation if such a permutation exists.

Input

The only input line contains an integer n�.

Output

Print a beautiful permutation of integers 1,2,…,n1,2,…,�. If there are several solutions, you may print any of them. If there are no solutions, print "NO SOLUTION".

Constraints

• 1≤n≤1e6

Example 1

Input:
5

Output:
4 2 5 3 1

Example 2

Input:
3

Output:
NO SOLUTION

 

Code

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    cin >> n;
    if (n == 1){
        cout << 1;
        return 0;
    }
    if (n == 2 || n == 3){
        cout << "NO SOLUTION";
        return 0;
    }
    int left = 1, right = n / 2 + 1;
    while (1){
        cout << right++ << " ";
        if (n % 2 && right > n) break;
        cout << left++ << " ";
        if (n % 2 == 0 && left > n / 2) break;
    } 
}

생각해야 하는 것

• 잘 관찰해보면 n이 2, 3인 경우를 제외한다면 beautiful한 순열을 만들 수 있음을 알 수 있습니다.
• 1부터 n까지의 수를 반으로 나눈 다음 번갈아 가면서 숫자들을 넣어준다면 우리가 원하는 순열을 만들 수 있습니다.
• 예외 케이스 : (1,2) 와 (3,4)로 나누었다면 큰 배열의 수를 먼저 써주어야 합니다. 그렇지 않으면 1, 3, 2, 4로 써지게 될텐데 여기서 3, 2의 차이가 1밖에 나지 않습니다. 큰 배열의 수를 먼저 써주면 3, 1, 4, 2 로 올바른 순열을 만들 수 있습니다.
• n 이 1인 경우 beautiful합니다.