[SWEA/C++] 2112. [모의 SW 역량테스트] 보호 필름Box에 담기 문제 풀기

 

문제

SWEA 문제

 

[문제 요약]

 

셀들은 특성 A와 B를 가지고 있으며 보호 필름의 성능은 셀들의 특성이 어떻게 배치되느냐에 따라 달라진다 셀의 특성이 같은 막이 한 열에 연속으로 K개 존재해야 보호 필름의 성능테스트를 통과하며 모든 열이 성능테스트를 통과해야 한다.

 

약품은 막 별로 투입할 수 있으며(행), 투입하는 막의 모든 셀들은 하나의 특성으로 변경된다. 성능테스트를 통과하기 위해 최소 약품 투입횟수는 몇인지 구하는 문제다.

 

 

풀이

 

[풀이]

 

각 행마다 약품을 주입 하지 않기, A약품을 주입, B약품을 주입 3가지 경우로 경우의 수를 나눴다.

 

그리고 모든 행의 경우가 정해지면 성능테스트를 통해 보호 성능검사를 통과 여부를 확인하고 통과한다면 약품 주입횟수를 이제까지 찾은 최소 약품 주입횟수와 비교해 작은 값을 저장했다.

 

그리고 중간에 가지치기를 통해 만약 현재 약품 주입 횟수가 최소 약품 주입 횟수보다 크거나 같다면 return하도록 코드를 짰다.

 

 

Code

 

 

#include <iostream>
using namespace std;

int D, W, K;
int lst[13][20] = { 0, };
int s_lst[13][20] = { 0, };
int min_ans;

bool test() {
	int base,cnt;
	for (int j = 0; j < W; j++) {
		base = s_lst[0][j];
		cnt = 1;
		if (cnt >= K) {
			break;
		}
		for (int i = 1; i < D; i++) {
			if (s_lst[i][j] == base) {
				cnt += 1;
				if (cnt >= K) {
					break;
				}
			}
			else {
				base = s_lst[i][j];
				cnt = 1;
			}
		}
		if (cnt<K) {
			return 0;
		}
	}
	return 1;
}

bool func(int deep, int ccnt) {
	if (ccnt >= min_ans) {
		return 0;
	}
	if (deep == D) {
		if (test()) {
			if (min_ans > ccnt) {
				min_ans = ccnt;
			}
		}
		return 0;
	}
	func(deep + 1, ccnt);
	
	for (int j = 0; j < W; j++) {
		s_lst[deep][j] = 0;
	}	
	func(deep + 1,ccnt+1);
	for (int j = 0; j < W; j++) {
		s_lst[deep][j] = lst[deep][j];
	}

	for (int j = 0; j < W; j++) {
		s_lst[deep][j] = 1;
	}
	func(deep + 1,ccnt+1);
	for (int j = 0; j < W; j++) {
		s_lst[deep][j] = lst[deep][j];
	}
	return 0;
}


int main() {
	int T,idx;
	cin >> T;
	for (int tc=1; tc<=T; tc++){
		min_ans = 21e7;
		cin >> D >> W >> K;
		for (int i = 0; i < D; i++) {
			for (int j = 0; j < W; j++) {
				cin >> idx;
				lst[i][j] =s_lst[i][j]= idx;
			}
		}
		func(0,0);
		cout <<"#"<<tc<<" "<<min_ans << "\n";
	}
}

 

---

 

C++이 익숙하지 않았을 때 풀었던 문제다..

 

뭔가 각 행의 경우의 수를 정하고 탐색해서 모든 행의 경우의 수를 정한 뒤에 test를 하는 것 보다 경우의 수를 하나 하나 선택할 때마다 test를 해보는게 더 빠를 것 같다고 생각 했는데 C++에 익숙해 지기 위해서 풀고 넘겼던 문제...

 

SW Expert Academy