CSES 1. Permutations (1070)

출처: https://cses.fi/problemset/task/1070

---

문제 설명

A permutation of integers 1,2,…,n is called beautiful if there are no adjacent elements whose difference is 1.

Given N, construct a beautiful permutation if such a permutation exists.

입력 양식

The only input line contains an integer N.

출력

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

입력 예

test1. 5 

test2. 3 

출력 예

test1. 4 2 5 3 1

test2. NO SOLUTION

제약조건

1 <=  n <= 1e6  

---

문제 풀이

N = 1 이면, 그냥 1을 출력 No distance, N=2 or N=3 -> No Solution, if N > 4 이면 짝수들을 2부터 2씩 커지는 순서로 N보다 작거나 같을 때까지 출력하고 1부터 나머지 홀수들을 2씩 증가시키면서 출력한다.

- 처음에는 next_permutation 함수를 써서 임의의 문자열에 대해서, 거리들을 측정했는데 숫자가 커지면서 TIME LIMIT EXCEEDED 가 나와서 그냥 만드는 방법으로 변경했다.

프로그램 내용

int main()
{
    int N;
    cin >> N;

    vector <int> numbers;			/// 1 ~ N
    for (int idx=0; idx< N; ++idx)
        numbers.push_back(idx+1);

    if (N == 1)
        cout << 1 << endl;
    else if (N==2 ||N == 3)
        cout << "NO SOLUTION" << endl;
    else
        for (int i=1; i < N; i += 2)	/// odd index
            cout << numbers[i] << " ";
        for (int i=0; i < N; i += 2)	/// even index
            cout << numbers[i] << " ";

 

Introductory problems ( link )