Educational Codeforces Round 106 (Rated for Div. 2) A

A. Domino on Windowsill

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n, k1, k2;
        cin >> n >> k1 >> k2;
        int w, b;
        cin >> w >> b;
        if(w+b > n){
            cout << "NO\n";
            continue;
        }
        int minw, maxw;
        minw = min(k1, k2);
        maxw = max(k1, k2);
        if(minw + (maxw-minw)/2 < w){
            cout << "NO\n";
            continue;
        }
        int minb, maxb;
        minb = min(n-k1, n-k2);
        maxb = max(n-k1, n-k2);
        if(minb + (maxb-minb)/2 < b){
            cout << "NO\n";
            continue;
        }
        cout << "YES\n";
    }
    return 0;
}

2 x n 크기의 격자가 있다. k1, k2 는 각 행의 흰색인 셀의 개수를 나타내고 w, b 는 2 x 1 크기의 흰, 검 도미노 타일의 개수를 나타낸다. 도미노 타일을 같은 색깔의 격자 위에 수직, 수평 방향으로 놓을 때, 주어진 개수만큼 모두 놓을 수 있는지를 묻고 있다.

도미노를 최대로 놓으려면 같은 색의 셀이 모여 있는것이 유리하다. 행마다 존재할 수 있는 셀의 개수는 정해져 있으므로 두 행의 셀을 각각 흰, 검 순서로 구분지었을 때가 타일을 최대로 놓을 수 있는 경우이다.

타일 개수가 작은 행의 셀 만큼 수직 방향으로 도미노를 놓을 수 있고, 타일 개수가 큰 행의 나머지 셀 / 2 개수만큼 수평으로 도미노를 놓을 수 있다.

후기

dp 문제가 나오면 설계하는 시간을 길게 가져야 할 것 같다. 너무 급하게 구현부터 하는 바람에 B번을 풀지 못했다. 오늘도 한 문제밖에 풀지 못했다.