[C++] 백준 21133번: N-Queen 2 - Ad-hoc

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

21133번: N-Queen 2

 

백트래킹 알고리즘을 통해 N-Queen 문제 (9633번)을 풀었다..

 N-Queen 2는 N-Queen의 심화 문제일거라 생각하고 문제를 읽었는데,

문제 조건은 그냥 n의 값이 커진 것과 시간제한이 확 줄어든 것을 보고 규칙찾기인가 싶었다.

그래서 하나하나 그려보며 규칙을 찾았던 와중, 가장 처음 찾은 규칙

n == even 이면 arr[2]부터 시작하여 2씩 증가하는 부분에 퀸을 놓고, n을 넘어가면 1부터 시작하여 퀸을 놓으면 된다.

n == odd 면  arr[1]부타 시작하여 2씩 증가하는 부분에 퀸을 놓고, n을 넘어가면 2부터 시작하여 퀸을 놓는다.

그래서 구현한 코드

#include <iostream>
using namespace std;
int main(){
    int n, i=1;
    cin >> n;
    if(n%2!=0){
        while(1){
            cout << i << "\n";
            i+=2;
            if(i>n){
                i-=n;
            }
            else if(i==n-1){
                cout << i;
                break;
            }
        }
    }
    else{
        i=2;
        while(1){
            cout << i << "\n";
            i+=2;
            if(i>n){
                i=1;
            }
            if(i==n-1){
                cout << i;
                break;
            }
        }
    }
}

 그랬더니 331 / 500의 점수가 나왔다.

어딘가 달라지는 부분이 있겠거니 싶어 다른 사람의 코드를 슬쩍 봤는데

6n + 2, 6n + 3인 경우에 따로 구현을 해주었다.

왜인지는 차차 알아보자..