boj 27468 2배 또는 0.5배

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

 

1 ~ N이 한번씩 등장하고, i, i + 1번째 수의 차이보다 i + 1, i + 2번째 수의 차이가 2배거나 0.5배인 수열을 만드는 문제입니다.

이 문제는 애드혹 문제로 직접 정답의 패턴을 찾을 수 있다면 구현 자체는 간단하게 할 수 있습니다.

 

저는 1부터 시작하여 정답을 찾던 도중

1 3 2 4 / 5 7 6 8 / 9 11 10 12 ... 이라는 패턴을 찾을 수 있었고, 4개 단위로 끊어서 정답을 구할 수 있다고 생각했습니다.

하지만 위의 정답은 반례가 하나 존재하며, N = 6, 10일 때를 보시면 7과 11이 6과 10보다 먼저 등장함을 알 수 있습니다.

따라서 N % 4 == 2인 경우와 N % 4 != 2인 경우를 분리하여 정답을 구했습니다.

 

N % 4 == 2일 때는 1 2 4 3 / 5 6 8 7 / 9 10 12 11 이라는 패턴을 찾을 수 있고, 이전 4개에서 +4를 한 값이 된다는 것을 알 수 있습니다.

그러면 찾은 패턴 2개를 그대로 코드에 옮겨주시면 되겠습니다.

 

 

#include <iostream>
using namespace std;
 
int list[4];
int N;
 
void init(int t) {
    if (t) {
        list[0] = 1;
        list[1] = 2;
        list[2] = 4;
        list[3] = 3;
    }
    else {
        list[0] = 1;
        list[1] = 3;
        list[2] = 2;
        list[3] = 4;
    }
    
}
 
void func() {
    init(N % 4 == 2);
 
    cout << "YES\n";
    int idx = 0;
    while (N--) {
        cout << list[idx] << ' ';
        list[idx] += 4;
        idx = (idx + 1) % 4;
    }
    cout << '\n';
}
 
void input() {
    cin >> N;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}