BOJ 1846 : 장기

• 문제 링크 : boj.kr/1846
• 난이도 : G4
• 태그 : 해 구성하기

1846번: 장기

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n;
    cin >> n;
    if(n == 3) {
        cout << -1;
        return 0;
    }
    
    int i = 1;
    for(; i < (n+1) / 2; i++) {
        cout << i+1 << "\n";
    }
    cout << "1\n" << n << "\n";
    for(; i < n-1; i++) {
        cout << i+1 << "\n";
    }

    return 0;
}

---

풀이

대각선에 놓을 수 없으면 대각선에 최대한 붙여서 놓으면 되는 거 아닌가? 에서 시작한 풀이이다.

 

대각선은 사각형을 네 부분으로 나눈다.

여기서 윗 부분은 왼쪽 대각선에, 아랫 부분은 오른쪽 대각선에 붙여서 말을 배치해보자.

N의 홀짝에 상관없이 가운데 두 줄에 말을 놓을 수 없게 된다.

이 두 줄에는 첫 번째 칸과 N번째 칸에 놓으면 쉽게 말을 놓을 수 있다.