(2112) [모의 SW 역량테스트] 보호 필름
레벨: 모의 역량 테스트
문제 🌐
성능이 우수한 보호 필름을 제작하려고 한다. 보호 필름은 [Fig.1]과 같은 엷은 투명한 막을 D장 쌓아서 제작된다.
막은 [Fig.1]과 같이 동일한 크기를 가진 바(bar) 모양의 셀들이 가로 방향으로 W개 붙여서 만들어진다.
이렇게 제작된 필름은 두께 D, 가로 크기 W의 보호 필름이라고 한다.
각 셀들은 특성 A 또는 특성 B를 가지고 있다. 보호 필름의 성능은 셀들의 특성이 어떻게 배치됨에 따라 결정된다.
[Fig.1]은 셀 6개를 이어서 만든 막의 단면이다.
[Fig.2]는 셀 8개로 이루어진 엷은 막 6장을 쌓아서 만든 두께 6, 가로크기 8인 보호 필름의 단면이다. A, B는 각 셀들이 가진 특성 A, 특성 B를 의미한다.
보호 필름의 성능을 검사하기 위해 합격기준 K라는 값을 사용한다. 충격은 보호 필름 단면의 세로 방향으로 가해지므로, 세로 방향 셀들의 특성이 중요하다. (충격방향은 [Fig.3]의 빨간색 화살표 참조)
단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과하게 된다.
[Fig.3]과 같이 보호 필름의 단면이 주어지고 합격기준 K값이 3으로 주어지는 경우를 생각해 보자. (예제 입력 1번과 동일)
세로 방향 ①, ②, ③, ④, ⑤, ⑥, ⑦, ⑧번 위치에는 동일한 특성을 지닌 셀이 3개 이상 연속적으로 있다. ([Fig.3]의 빨간색 사각형 참조)
하지만 ④번 위치는 동일한 특성을 지닌 셀이 3개 이상 연속적으로 있지 않으므로 성능 검사를 통과할 수 없다.
성능검사에 통과하기 위해서 약품을 사용하여야 한다.
약품은 막 별로 투입할 수 있으며 이 경우 투입하는 막 모든 셀들은 하나의 특성으로 변경된다.
특정 막에 약품 A를 투입하면 막 내의 모든 셀들이 특성 A로 변경되며, 약품 B를 넣게 되면 특성이 모두 특성 B로 변경된다.
[Fig.4]는 세 번째 막에 약품 A를 투입하여 특성 A로 변경하고, 여섯 번째 막에 약품 B를 투입하여 특성 B로 변경시킨 경우이다.
약품 투입횟수 두 번으로 ①~⑧번까지의 모든 세로방향에 대해서 동일한 특성의 셀들이 연속적으로 3개 이상 있기 때문에 성능 검사를 통과하였다. (합격기준 K=3)
[Fig.3]의 경우 약품을 투입하여 성능검사를 통과시키는 방법은 여러 방법이 있을 수 있지만 투입 횟수의 최소값은 2이다.
따라서 성능검사를 통과하기 위한 최소 약품투입 횟수는 2가 된다.
두께 D, 가로크기 W인 보호 필름 단면의 정보와 합격기준 K가 주어졌을 때, 약품 투입 횟수를 최소로 하여 성능검사를 통과할 수 있는 방법을 찾고,
이때의 약품 투입 횟수를 출력하라. ([Fig.3] 예제의 경우 정답은 2가 된다.)
약품을 투입하지 않고도 성능검사를 통과하는 경우에는 0을 출력한다.
제약사항
시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 5초
보호 필름의 두께 D는 3이상 13이하의 정수이다. (3≤D≤13)
보호 필름의 가로크기 W는 1이상 20이하의 정수이다. (1≤W≤20)
합격기준 K는 1이상 D이하의 정수이다. (1≤K≤D)
셀이 가질 수 있는 특성은 A, B 두 개만 존재한다.
입력
첫 줄에 총 테스트 케이스의 개수 T가 주어진다.
두 번째 줄부터 T개의 테스트 케이스가 차례대로 주어진다.
각 테스트 케이스의 첫 줄에는 보호 필름의 두께 D, 가로크기 W, 합격기준 K가 차례로 주어진다.
그 다음 D줄에 보호 필름 단면의 정보가 주어진다. 각 줄에는 셀들의 특성 W개가 주어진다. (특성A는 0, 특성B는 1로 표시된다.)
출력
테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.
각 줄은 “#x”로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)
출력해야 할 정답은 성능검사를 통과할 수 있는 약품의 최소 투입 횟수이다. 약품을 투입하지 않고도 성능검사를 통과하는 경우에는 0을 출력한다.
접근 방법
문제 풀이 방법은 다음과 같다.
- 약품을 주입할 행의 개수와 조합 구하기 (0개~D개, A, B, AA, AB, BA, BB, …)
- 약품을 주입하고 품질 검사에 맞는지 판별하기
따라서 메인 메소드 외에 3가지의 메소드를 만들었다.
filmChk보호 필름이 조건에 일치하는가 확인combination0~D 범위의 숫자 중 0~D개를 선택하는 숫자 조합binary각각의 행을 A로 채울지, B로 채울지 결정
일단 굉장한 시간 초과 이슈가 발생했다. 무려 50개 TC 중 50개가 맞았지만 시간 초과로 틀린 적도 있었다.
조합을 0개, 1개, 2개, … 를 모두 구하면서 필름의 유효성을 체크한 것, 복제한 필름 배열에서 매번 2차원 배열 탐색으로 값을 초기화하려 한 것이 문제였다.
그래서 조합을 만들자마자 바로 유효성을 체크하고, 불필요한 연산을 줄였다.
필름에 시약을 주입하는 과정에서도, A와 B로 채워진 W 크기의 char[] 배열을 만들어 두고, 필름에 대한 정보를 받아올 때도 originalFilm과 film 두 가지를 만들어 film에 A, B 배열을 각각 알맞게 덮어씌우고 검사가 끝나면 바꾼 행만 originalFilm에서 값을 가져와서 원래대로 복구하는 방식으로 변경했다.
사실 조합을 구할 때 비트마스킹을 사용했다면 시간 초과 이슈는 만나지 않았을 거란 걸… 알고 있음에도 애써 부정하고 싶다. 다음에는 조합 문제를 풀 때 비스마스킹을 활용해서 해 봐야겠다.
태초의 코드…
import java.util.Arrays;
import java.util.Scanner;
public class Solution {
static int D;
static int W;
static int K;
static boolean[] chk;
static boolean[][] film;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
D = sc.nextInt();
W = sc.nextInt();
K = sc.nextInt();
int answer = K;
// true면 B false면 A
film = new boolean[D][W];
chk = new boolean[D];
for (int i = 0; i < D; i++) {
for (int j = 0; j < W; j++) {
int temp = sc.nextInt();
if (temp == 1)
film[i][j] = true;
else
film[i][j] = false;
}
}
for (int i = 0; i <= K; i++) {
int[] result = new int[i];
boolean[] ab = new boolean[i];
if (combination(0, i, 0, result, ab)) {
answer = i;
break;
}
}
System.out.println("#"+test_case+" "+answer);
}
}
public static boolean filmChk(boolean[][] film) {
boolean[] chk = new boolean[W];
boolean answer = true;
for (int c = 0; c < W; c++) {
boolean isOkay = false;
int cnt = 1;
for (int r = 1; r < D; r++) {
if (film[r - 1][c] == film[r][c])
cnt++;
else
cnt = 1;
if (cnt >= K)
isOkay = true;
}
if (isOkay)
chk[c] = true;
}
for (int i = 0; i < W; i++) {
if (!chk[i])
answer = false;
}
return answer;
}
public static boolean combination(int cnt, int num, int start, int[] result, boolean[] ab) {
boolean temp = false;
if (cnt == num) {
temp = binary(num, ab, result);
} else {
for (int i = start; i < D; i++) {
result[cnt] = i;
ab[cnt] = true;
boolean tempResult = combination(cnt + 1, num, i + 1, result, ab);
if (tempResult) return true;
ab[cnt] = false;
tempResult = combination(cnt + 1, num, i + 1, result, ab);
if (tempResult) return true;
}
}
return temp;
}
public static boolean binary(int num, boolean[] ab, int[] result) {
boolean[][] tempFilm = new boolean[D][W];
for (int i = 0; i < D; i++) {
for (int j = 0; j < W; j++)
tempFilm[i][j] = film[i][j];
}
for (int i = 0; i < num; i++) {
int r = result[i];
boolean set = ab[i];
for (int c = 0; c < W; c++) {
tempFilm[r][c] = set;
}
}
boolean chkResult = filmChk(tempFilm);
return chkResult;
}
}
Full Solution
import java.util.Arrays;
import java.util.Scanner;
public class Solution {
static int D;
static int W;
static int K;
static boolean[] chk;
static boolean[][] film;
static boolean[][] OFilm;
static boolean[] A;
static boolean[] B;
static int answer;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int test_case = 1; test_case <= T; test_case++) {
D = sc.nextInt();
W = sc.nextInt();
K = sc.nextInt();
answer = K;
// true면 B false면 A
film = new boolean[D][W];
OFilm = new boolean[D][W];
A = new boolean[W];
B = new boolean[W];
for (int i=0; i<W; i++) {
B[i] = true;
}
chk = new boolean[D];
for (int i = 0; i < D; i++) {
for (int j = 0; j < W; j++) {
int temp = sc.nextInt();
if (temp == 1) {
film[i][j] = true;
OFilm[i][j] = true;
} else {
film[i][j] = false;
OFilm[i][j] = false;
}
}
}
int[] result = new int[K];
boolean[] ab = new boolean[K];
combination(0, 0, result, ab);
System.out.println("#" + test_case + " " + answer);
}
}
public static void combination(int cnt, int start, int[] result, boolean[] ab) {
if (cnt >= answer || cnt==K) return;
boolean temp = false;
temp = binary(cnt, ab, result);
if (temp) {
answer = Math.min(answer, cnt);
}
for (int i = start; i < D; i++) {
result[cnt] = i;
ab[cnt] = true;
combination(cnt + 1, i + 1, result, ab);
ab[cnt] = false;
combination(cnt + 1, i + 1, result, ab);
}
}
public static boolean binary(int num, boolean[] ab, int[] result) {
for (int i = 0; i < num; i++) {
int r = result[i];
boolean set = ab[i];
if (set) film[r] = B;
else film[r] = A;
}
boolean chkResult = filmChk(film);
for (int i=0; i<num; i++) {
int r = result[i];
film[r] = OFilm[r];
}
return chkResult;
}
public static boolean filmChk(boolean[][] film) {
boolean[] chk = new boolean[W];
boolean answer = true;
for (int c = 0; c < W; c++) {
boolean isOkay = false;
int cnt = 1;
for (int r = 1; r < D; r++) {
if (film[r - 1][c] == film[r][c])
cnt++;
else
cnt = 1;
if (cnt >= K)
isOkay = true;
}
if (isOkay)
chk[c] = true;
}
for (int i = 0; i < W; i++) {
if (!chk[i])
{
answer = false;
break;
}
}
return answer;
}
}