BOJ 10589 : 마법의 체스판

• 문제 링크 : boj.kr/10589
• 난이도 : G4
• 태그 : 애드혹, 해 구성하기

10589번: 마법의 체스판

---

코드

#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, m;
    cin >> n >> m;

    cout << n/2 + m/2 << "\n";
    for(int i = 2; i <= n; i += 2) {
        cout << i << " 1 " << i << " " << m << "\n";
    }
    for(int i = 2; i <= m; i += 2) {
        cout << "1 " << i << " " << n << " " << i << "\n";
    }

    return 0;
}

---

풀이

3*3의 체스판으로 단순화해서 생각해보자. 이는 #모양에서 모든 선분을 홀수번 칠하는 것과 같다.

이때 가장 최적은 모든 선분을 딱 한 번씩 칠하는 것이다.

어떻게 칠하더라도 길게 이어진 선분을 나눠서 칠하는 것은 비효율적임을 알 수 있다. 따라서 길게 이어진 선분은 한 번에 칠해야 하고, 평행한 두 선분을 동시에 칠하게 된다.

평행한 긴 선분 두개씩 동시에 칠하는 모든 방법은 유효한 방법이므로 아무렇게나 칠하면 된다.