[SWEA] 보호필름

SWEA 보호필름 C++ 풀이

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

 

// 브루트 포스 재귀 문제이다.
// 치킨 배달 문제와 굉장히 비슷 하다.
// 먼저 값을 받고 solve 함수에 (depth, cnt)로 놓고 함수 안에는 기저 조건으로 cnt가 ans보다 크게 되면 종료하게 되고
// depth가 D와 같아졌을때 검사를 한다. 일단 temp로 map과 같은 크기의 배열을 놓고 여기에 change를 통해 바뀐 값을 넣어 check()에서 확인을 한다.
#include <iostream>
#include <algorithm>

using namespace std;

int map[14][21];
int temp[14][21];

int change[14];

int D, W, K, ans;

bool check() {

	int cnt;

	for (int i = 0; i < W; i++) {
		cnt = 1;
		for (int j = 1; j < D; j++) {
			if (cnt >= K)
				break;

			if (temp[j - 1][i] == temp[j][i])
				cnt++;
			else
				cnt = 1;
		}
		if (cnt < K)
			return false;
	}
	return true;
}

void solve(int depth, int cnt) {

	if (cnt > ans)
		return;

	if (depth == D) {
		for (int i = 0; i < D; i++) {
			for (int j = 0; j < W; j++) {
				if (change[i] != -1) {
					temp[i][j] = change[i];
				}
				else {
					temp[i][j] = map[i][j];
				}

			}
		}

		if (check()) { // 바뀐것마다 check 해야되기 때문에 return을 {}안에 두면 안된다.
			ans = min(ans, cnt);
		}

		return;

	}

	change[depth] = -1; // 약 투여 x
	solve(depth + 1, cnt);
	change[depth] = 0; // A 투여
	solve(depth + 1, cnt + 1);
	change[depth] = 1; // B 투여
	solve(depth + 1, cnt + 1);
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int T;

	cin >> T;

	for (int tc = 1; tc <= T; tc++) {
		cin >> D >> W >> K;

		ans = 98798797;

		for (int i = 0; i < D; i++) {
			for (int j = 0; j < W; j++) {
				cin >> map[i][j];
			}
		}

		solve(0, 0);


		cout << "#" << tc << " " << ans << "\n";
	}
	return 0;
}