# 격자 색칠

# 문제

 

# 입력 및 출력

 

# 풀이

일단 해당 조건을 만족하기 위해선 가로든 세로든 같은 색으로 2줄 이상 칠해져야 한다.

그래서 2줄 이상 칠해져야 한다는 조건을 만족하기 위해 일단 2줄씩은 무조건 색칠하도록 했다.

그래서 사용한 배열이 cnt 배열이다.

같은 줄을 몇 줄이나 칠할 수 있는 지 세는 배열이다.

같은 줄을 2줄 이상 칠할 수 있는 경우엔 2줄씩 먼저 색칠하고 그 다음에도 색칠을 다 못한 경우가 있을 땐

2줄보다 더 많이 칠할 수 있는 색으로 전부 색칠하면 된다.

 

색을 칠할 때 2줄 이상이 되면 홀수가 되든 짝수가 되든 상관이 없기 때문이다.

말이 좀 헷갈리는데 6줄을 칠해야 하는 경우라면

1. 2-2-2

2. 2-4

3. 3-3

이런 방법으로 색칠할 수 있다.

처음 코딩할 땐 3번의 경우가 굉장히 헷갈렸는데, 위 방식대로 하면 따로 신경쓰지 않아도 된다.

왜냐하면 색이 2개밖에 없어 2-2로만 칠한 상태에서 1개씩 더 칠하면 되기 때문이다.

 

#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("grid.inp");
ofstream fout("grid.out");

bool check(int n, int m, int k, int p[100000]) {
	int line = n;
	int cnt[100000];
	for (int i = 0; i < k; i++) {
		cnt[i] = p[i] / m; // 몇 줄을 칠할 수 있는지
	}
	for (int i = 0; i < k; i++) {
		if (cnt[i] >= 2 && line >= 2) { // 처음엔 2줄씩 색칠함
			line -= 2;
		}
		if (line == 0) break;
	}
	if (line >= 1) {
		for (int i = 0; i < k; i++) {
			if (cnt[i] >= 3) { // 3줄 이상 채울 수 있는 경우엔
				line -= cnt[i] - 2; // 처음 칠했던 2줄 빼고 나머지 전부 색칠
			}
			if (line <= 0) break;
		}
	}
	if (line <= 0) return true;
	else return false;
}

int main() {
	int t, n, m, k;
	fin >> t;
	while (t--) {
		fin >> n >> m >> k;
		int paint[100000];
		for (int i = 0; i < k; i++) {
			fin >> paint[i];
		}
		sort(paint, paint + k, greater<int>());
		bool res = check(n, m, k, paint) || check(m, n, k, paint); // 가로, 세로 둘 다 확인
		if (res) fout << "Yes" << "\n";
		else fout << "No" << "\n";
	}
}

 

이전 달팽이 문제보다 더 어려웠던 것 같다..