[백준] 27468번 : 2배 또는 0.5 배 (C++)

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

 

문제

KSA 학생들은 아래 조건을 만족하는 길이가 N인 수열을 좋아한다.

•  1,2,⋯,N이 A에 정확히 한 번씩 등장한다.
• 임의의 인접한 세 수 A_i, A_{i+1}, A_{i+2}에 대해 |A_{i+1}−A_i|=|A_{i+2}−A_{i+1}|×2 또는  |A_{i+1}−A_i|=|A_{i+2}−A_{i+1}|×0.5이다.

정수 N이 주어졌을 때, 조건을 만족하는 수열이 존재하는지 판별하고 있다면 아무거나 찾아보자.

입력

첫 번째 줄에 정수 N이 주어진다.

출력

첫 번째 줄에 조건을 만족하는 수열이 존재한다면 YES, 아니라면 NO를 출력한다.

만약 그러한 수열이 존재한다면, 두 번째 줄에 N개의 정수 A1,A2,⋯,AN출력한다.

정답이 여러 개 존재한다면 아무거나 출력해도 상관없다.

제한

•  3≤N≤2×10^6

서브태스크

번호배점제한

1	7	N≤10
2	33	N은 4의 배수
3	60	추가 제약 조건 없음

예제 입력 1 

4

예제 출력 1 

YES
3 1 2 4

예제 입력 2 

16

예제 출력 2 

YES
1 2 4 8 6 5 7 3 11 15 13 14 16 12 10 9

---

처음에는 브루트포스로 그냥 찾다보면 수열을 얻을 수 있을 것이라 생각했지만, 일일히 찾다보면 TLE가 날 것 같았다.

그래서 그냥 하나하나 수열을 만들어 보았다.

 

노드를 연결하는 패턴을 보니 1, 2, 1, 2, ... 혹은 2, 1, 2, 1, ...의 패턴이면 모든 수열을 만들 수 있을 것 같았다.

 

그래서 패턴을 두개로 나누어 배열을 만들었고, 두 패턴중에 맞는 패턴을 찾아서 배열을 출력하면 된다.

 

#include <bits/stdc++.h>

using namespace std;

int n;

int c[2020202];

int pattern1[4] = {1,2,-1,2};

int pattern2[4] = {2,-1,2,1};

queue<int> q;

int sol(int pattern[4]){

    q.push(1);

    for(int i = 0 ; i <= n ; i++) c[i]=0;

    bool flag = true;

    int i = 1;

    for(int j = 0 ; j < n-1 ; j++){

        int a = pattern[j%4];

        i+=a;

        if(i<=n && c[i]==0){

            c[i]=1;

            q.push(i);

        }

        else{

            return 1;

        }

    }

    return 0;

}

int main(void){

    cin>>n;

    int res1 = sol(pattern1);

    int res2;

    if(res1==1){

        while(!q.empty()) q.pop();

        res2 = sol(pattern2);

    }

    else{

        cout<<"YES\n";

        while(!q.empty()){

            cout<<q.front()<<" ";

            q.pop();

        }

        return 0;

    }

    if(res2==1){

        cout<<"NO";

    }

    else{

        cout<<"YES\n";

        while(!q.empty()){

            cout<<q.front()<<" ";

            q.pop();

        }

        return 0;

    }

}

 

 

사실 NO가 나올 일은 없지만 그래도 예의상 코드를 짜긴 했다.