$\frac{1}{2}$(MatKor+ALPS)=AlKor

문제 분석 및 풀이

설계 분석

평소에 풀던 유형도 아니고 자주 나오는 유형도 아니지만 풀이과정이 재미있어서 기록하는 문제

• $2\leq 10^4$ 이므로 $O(NlogN)$까지가 무난

• $A_{n+1} = \frac{A_{1} + A_{2} + ... + A_{N}}{N}$ 를 만족하는 수열을 만드는 문제

• $A_i$의 범위가 넓어서 무조건 찾을 수 있는데 어떻게 코드로 모든 N에 대해서 찾는지 찾아야함

• 위의 식을 정리해보면 $NA_{n+1} = A_{1} + A_{2} + ... + A_{N}$ 이 식을 간편하게 바꿔보자

• $A_{n+1} = 0$ 이면 $A_{1} + A_{2} + ... + A_{N} = 0$ 이라는 아주 아름다운(?) 식이 만들어진다.

• 그 뒤로는 (-1,1), (-2,2) 처럼 짝을 맞춰서 합이 0이 되도록 추가하면 된다.

• 최종 형태는 i -i j -j k -k 0 형태의 수열을 찾는다.

• 단 홀수인 경우 3개를 더해서 0이 되는 경우를 넣고 남은 개수를 짝수로 만들어 위의 과정을 진행

• $O(N)$

풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int N;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    /*
    NAn+1 = A1 + A2 + ... + AN을 만족하는 수열을 찾는 문제
    후보군이 충분히 넓으니 An+1 = 0 을 만족하는 조건을 찾자
    즉 A1 + A2 + ... + AN = 0이 되도록 설정하자
    그렇다면 
    i -i j -j k -k ... 0 형태의 수열을 찾아낼 수 있다.
    여기서 홀수인 경우 -9 8 1같이 3개를 더해 0이 되는 경우을 미리 넣어서 남은 개수를 짝수개로 만들어서
    i-i같이 짝을 맞춰 수열을 구성한다.
    */

    cin >> N;
    // 홀수인 경우
    if (N & 1)
    {
        cout << -100 << ' ' << 1 << ' ' << 99 << ' ';
        N-=3;
    }

    for (int i = 101, cnt = 1; cnt <= N / 2 ; i++, cnt++)
    {
        int pairAi = i;
        cout << pairAi << ' ' << -1 * pairAi << ' ';
    }
    
    cout << 0 ;
    
    return 0;
}