SWEA 2112번: [모의 SW 역량테스트] 보호 필름

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

SW Expert Academy

SWEA 내의 문제 중 두 번째로 고생한 문제당 😢

처음에 시간초과 때문에 당황해서 더 헤멘 문ㅈㅔ ~~ ㅠㅠ

왼쪽 그림처럼 셀의 특성이 주어졌을 때, 셀들에 약품을 주입해서 해당 열을 모두 한 상태로 만든 뒤

모든 열이 K개 이상 연속함을 만족하는 약품 주입 횟수의 최소값!을 구해야 한다

수도코드를 10분 안에 작성해서 오 뭐야 하고 바로 제출했는데 시간초과 떴다 ㅠㅠ

댓글 보면서 틀린점 분석하면서 삽질하고 헤매다가 결국 처음 코드에서 시간초과만 조금 줄여주고 성공......

⭐저번에 얻은 팁⭐ 순열 여러 개 구할때는 시간복잡도를 줄여주자

실전이었음 큰 ㅠㅠㅠ 일 ㅠㅠㅠ 날 ㅠㅠㅠㅠㅠ 뻔 ㅠㅠㅠ

#include <cstdio>
int tc, d, w, k,ans,ins;
int f[10];
bool map[14][21];
bool continous() {
	for (int j = 0; j <w; j++) {
		int count = 1;
		for (int i = 1; i < d; i++) {
			if (count >= k)break;
			if (map[i][j] == map[i - 1][j])
				count++;
			else count = 1;
		}
		if (count < k)return false;
	}
	return true;
}
void simulator(int t,int dep) {
	if (ans != -1)return;
	if (dep == ins) {
		if (continous())ans = ins;
		return;
	}

	bool temp[21];
	for (int i = t; i < d; i++) {
		f[dep] = i;
		for (int j = 0; j < w; j++)temp[j] = map[i][j];
		for (int j = 0; j < w; j++)map[i][j] = 0;
		simulator(i+1,dep + 1);
		for (int j = 0; j < w; j++)map[i][j] = 1;
		simulator(i+1,dep + 1);
		for (int j = 0; j < w; j++)map[i][j]= temp[j];
	}
}
int main() {
	scanf("%d", &tc);
	for (int T = 1; T <= tc; T++) {
		ans = -1; ins = 0;
		scanf("%d%d%d", &d, &w, &k);
		for(int i=0;i<d;i++)
			for (int j = 0,a; j < w; j++)
				scanf("%d", &map[i][j]);

		while (ans==-1&&!continous()) {
			ins++;
			simulator(0,0);
		}

		printf("#%d %d\n", T, ans==-1?0:ans);
	}
	return 0;
}

 

남은 기간동안 열심히해서 취뽀하자

힘내라 나 자신.....