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

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu&categoryId=AV5V1SYKAaUDFAWu&categoryType=CODE

SW Expert Academy

1. 유형

부분집합, 구현

 

2. 풀이

• 행 하나를 선택한 후, 아무것도 안하기, A약 투입, B약 투입 인 경우로 나눈다
• 위의 경우를 부분집합을 구한다
• K개 만큼 연속하는지 판단

또한, 잘 구현하더라도 효율성 체크에서 걸릴 것이다.

이때,

• K==1인 경우 바로 0출력
• 재귀에서 cnt가 더 큰 경우 빽트래킹
• 연속을 판단할때 col하나라도 연속하지 않으면 빽트래킹

이 3가지 조건을 다 만족해야 pass를 받을 수 있다.

 

조건 판단

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int T, res;
	static int D, W, K, map[][];

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		T = Integer.valueOf(st.nextToken());
		for (int tc = 1; tc <= T; tc++) {
			st = new StringTokenizer(in.readLine(), " ");
			D = Integer.valueOf(st.nextToken());
			W = Integer.valueOf(st.nextToken());
			K = Integer.valueOf(st.nextToken());
			map = new int[D][W];
			for (int i = 0; i < D; i++) {
				st = new StringTokenizer(in.readLine(), " ");
				for (int j = 0; j < W; j++) {
					map[i][j] = Integer.valueOf(st.nextToken());
				}
			}
			res = Integer.MAX_VALUE;
			int cnt = 0;
			if (K == 1) {
				System.out.println("#" + tc + " " + "0");
			} else {
				comb(0, 0);
				System.out.println("#" + tc + " " + res);
			}
		}
	}

	static boolean checkPass() {
		int total = 0;
		for (int j = 0; j < W; j++) {
			int cnt = 1;
			boolean flag = false;
			for (int i = 1; i < D; i++) {
				if (map[i][j] == map[i - 1][j]) {
					cnt++;
				} else {
					cnt = 1;
				}
				if (cnt >= K) {
					total++;
					flag = true;
					break;
				}
			}
			if (!flag) {
				return false;
			}
		}
		if (total == W)
			return true;
		else
			return false;
	}

	static void comb(int arr_idx, int cnt) {
		if (res < cnt) {
			return;
		}
		if (arr_idx == D) {
			if (checkPass()) {
				res = res > cnt ? cnt : res;
			}
			return;
		}
		//원래 배열중에서 한 행을 복사
		int tmp[] = new int[W];
		for (int j = 0; j < W; j++) {
			tmp[j] = map[arr_idx][j];
		}

		// 아무것도 안 넣음
		comb(arr_idx + 1, cnt);

		// a넣음
		for (int j = 0; j < W; j++) {
			map[arr_idx][j] = 0;
		}
		comb(arr_idx + 1, cnt + 1);

		// b넣음
		for (int j = 0; j < W; j++) {
			map[arr_idx][j] = 1;
		}
		comb(arr_idx + 1, cnt + 1);
		
		//a와 b를 넣어서 바뀐 행을 원상복귀
		for (int j = 0; j < W; j++) {
			map[arr_idx][j] = tmp[j];
		}
	}
}

4. 느낀점

 

보고나서 부분집합을 떠올리긴 했는데, 아무것도 하지 않는 경우는 생각하지 못했다.

더 분발해야겠다.