문제 설명
다섯 개의 정수 n, k1, k2, w, b가 주어진다고 가정해 봅시다. 2×n 크기의 보드가 있으며, 첫 번째 행의 앞 k1개 셀과 두 번째 행의 앞 k2개 셀은 흰색으로 칠해져 있고, 나머지 셀은 모두 검은색입니다.
우리는 흰색 도미노 w개와 검은색 도미노 b개(각각 2×1 크기)를 가지고 있습니다.
- 흰색 도미노는 덮으려는 두 셀이 모두 흰색이고, 다른 도미노가 이미 놓여 있지 않은 경우에만 배치할 수 있습니다.
- 검은색 도미노 역시 두 셀이 모두 검은색이고 비어 있어야 배치할 수 있습니다.
도미노는 가로 또는 세로 어느 방향으로든 놓을 수 있을 때, 모든 w + b개의 도미노를 보드 위에 배치할 수 있는지 판별해야 합니다.
예를 들어 입력이 n = 5, k1 = 4, k2 = 3, w = 3, b = 1이라면 출력은 True(참)가 됩니다.
접근 방법
이 문제의 핵심은 의외로 간단합니다. 도미노는 가로·세로 어느 방향으로든 자유롭게 배치할 수 있기 때문에, 필요한 셀의 개수만 충분하다면 실제 배치는 항상 가능하기 때문입니다.
- 흰색 도미노 한 개는 흰색 셀 2개를 차지하므로, 흰색 도미노 w개를 놓으려면 전체 흰색 셀(k1 + k2)이 최소 2 × w개 이상 있어야 합니다.
- 마찬가지로 검은색 도미노 b개를 놓으려면 전체 검은색 셀((n − k1) + (n − k2))이 최소 2 × b개 이상 있어야 합니다.
이 두 조건이 동시에 만족되면 모든 도미노를 배치할 수 있습니다.
알고리즘
문제를 해결하기 위해 다음 단계를 따릅니다.
if 2 * w <= (k1 + k2) and 2 * b <= (n - k1 + n - k2), then:
return true
Otherwise
return false
C++ 구현 예제
더 나은 이해를 돕기 위해 다음 C++ 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
bool solve(int n, int k1, int k2, int w, int b) {
if (2 * w <= (k1 + k2) && 2 * b <= (n - k1 + n - k2)) {
return true;
}
else {
return false;
}
}
int main() {
int n = 5;
int k1 = 4;
int k2 = 3;
int w = 3;
int b = 1;
cout << solve(n, k1, k2, w, b) << endl;
}
입력
5, 4, 3, 3, 1
출력
1
결과 분석
위 예제에서 흰색 셀은 총 k1 + k2 = 7개이고, 흰색 도미노 3개에는 6개의 셀이 필요하므로 첫 번째 조건을 만족합니다. 검은색 셀은 (5 − 4) + (5 − 3) = 3개이고, 검은색 도미노 1개에는 2개의 셀이 필요하므로 두 번째 조건도 만족합니다. 따라서 함수는 참(1)을 반환하고, 모든 도미노를 보드에 배치할 수 있습니다.