[C++] [CSES] Two Sets (Introductory Problems)

CSES의 여덟번째 문제입니다.

1 ~ n 까지 자연수들을 두 집합으로 나누어 집합 안에 있는 수의 합이 같게 나누어야 하는 문제입니다.

 

Task

Your task is to divide the numbers 1,2,…,n into two sets of equal sum.

Input

The only input line contains an integer n.

Output

Print "YES", if the division is possible, and "NO" otherwise.

After this, if the division is possible, print an example of how to create the sets. First, print the number of elements in the first set followed by the elements themselves in a separate line, and then, print the second set in a similar way.

Constraints

• 1≤n≤1e6

Example 1

Input:
7

Output:
YES
4
1 2 4 7
3
3 5 6

Example 2

Input:
6

Output:
NO

 

Code

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

int n;
void calc(int n){
    vector<int> fir, sec;
    int cur;
    if (n % 4 == 3){
        fir.push_back(1);
        fir.push_back(2);
        sec.push_back(3);
        cur = 4;
    }
    else{
        fir.push_back(1);
        fir.push_back(4);
        sec.push_back(2);
        sec.push_back(3);
        cur = 5;
    }
    for (int i=cur;i<=n;i+=4){
        fir.push_back(i);
        fir.push_back(i+3);
        sec.push_back(i+1);
        sec.push_back(i+2);
    }
    cout << "YES\n";
    cout << fir.size() << "\n";
    for (int a : fir) cout << a << " ";
    cout << "\n";
    cout << sec.size() << "\n";
    for (int a : sec) cout << a << " ";
}
int main(){
    cin >> n;
    if (n % 4 == 1 || n % 4 == 2){
        cout << "NO";
        return 0;
    }
    calc(n);
}

생각해야 하는 것

• 우선 4로 나누었을 때 나머지가 1 이나 2 이면 1 ~ n 의 합이 홀수이기 때문에 합이 같게 나눌 수 없습니다.
• 다른 경우에는 합이 같게 나눌 수 있는데, 이는 연속된 n, n+1, n+2, n+3 은 바깥 두 수와 안쪽 두 수를 더하면 2 * n + 3으로 같음을 이용합니다.
• 초기값 설정을 잘 해주어야 합니다. 1, 2, 3인 경우 (1, 2)와 (3)으로 나눌 수 있고, 1, 2, 3, 4인 경우 (1, 4)와 (2, 3)으로 나눌 수 있습니다.