문제 개요
보호 필름의 성능을 검사하기 위해 합격기준 K라는 값을 사용한다.
충격은 보호 필름 단면의 세로 방향으로 가해지므로, 세로 방향 셀들의 특성이 중요하다.
단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과하게 된다.
성능검사에 통과하기 위해서 약품을 사용하여야 한다.
약품은 막 별로 투입할 수 있으며 이 경우 투입하는 막의 모든 셀들은 하나의 특성으로 변경된다.
특정 막에 약품 A를 투입하면 막 내의 모든 셀들이 특성 A로 변경되며, 약품 B를 넣게 되면 특성이 모두 특성 B로 변경된다.
두께 D, 가로크기 W인 보호 필름 단면의 정보와 합격기준 K가 주어졌을 때, 약품 투입 횟수를 최소로 하여 성능검사를 통과할 수 있는 방법을 찾고,
이때의 약품 투입 횟수를 출력하라.
약품을 투입하지 않고도 성능검사를 통과하는 경우에는 0을 출력한다.
중요한 부분은 강조해놓았지만, 다시 한번 정리해보자.
- 똑같은 특성의 막이 연속 K가 있는 단면은 통과, 그렇지 않으면 기준미달이다
- 기준을 충족시키기 위해 약품을 투입할 것, 이때 약품 투입 횟수가 최소가 되도록 해야한다.
문제 풀이
이 문제의 핵심은 두가지 부분으로 나누어진다
- 성능검사
- 어떤 약물을 몇번 어디에 투입할것인가?
성능검사의 경우, 중요한 부분이 있다. 하나의 막이라도 통과하지 못할 경우 기준미달이라는 사실이다. 이 부분은 백트래킹을 하는 과정에 있어서 매우 중요하다. 이 부분을 검사해주지 않으면 시간 복잡도가 미친듯이 치솟기 때문이다.
실제로,이 부분을 처리 해준 다음 처리시간이 반이 줄었다.
약물주입 부분의 경우, 1)약물을 주입하지 않는다 2) A 약물을 주입한다 3) B 약물을 주입한다 세가지 경우의 수를 넣어주어야 한다.
반드시 약물을 주입하지 않는다는 경우의 수를 고려해주어야 한다!!
더불어 약물주입을 직접 하지 않아야 한다. 어떤 약물을 어떤 위치에 주입할지를 가지고 있는 배열을 이용하여 약물을 주입할 것인데, 이것이 최소주입횟수를 가지는 경우의 수인지 알 수 없기 때문에 원본 필름의 값을 훼손하지 않아야한다.
그렇기 때문에 임시 필름 배열을 만들어 놓은 다음, 주입여부배열을 이용하여 새로운 임시필름에 값을 입력해주어야한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* @author 신온유
* @performance
* @category
* @note
* 성능검사 -> 동일한 특성의 셀들이 K(합격기준)개 이상 연속적으로 있는 경우 통과함
* 약품투약 -> 하나의 특성으로 한줄이 변함
* 최소 투입 횟수를 구하자
* 1.약품을 어디에 투입할지 조합을 구한다
* 2.성능검사를 약품을 투약할때마다 시행한다
* @see
* https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu&categoryId=AV5V1SYKAaUDFAWu&categoryType=CODE&&&
* @since 2023/10/11
**/
public class 보호필름 {
static int T,D,W,K;
static int[][] film;
static int[] arr; // 주입할 위치를 정하는 배열
static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for(int t=1;t<T+1;t++){
st = new StringTokenizer(br.readLine()," ");
D = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken()); // 통과기준
film = new int[D][W];
arr = new int[D];
answer = Integer.MAX_VALUE; // 최소값
for(int i=0;i<D;i++){
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<W;j++){
film[i][j] = Integer.parseInt(st.nextToken());
}
}
Arrays.fill(arr,-1);
if(!isPass()) dfs(0,0);
else answer = 0;
System.out.printf("#%d %d\n",t,answer);
}
}
static void dfs(int depth,int idx){
//idx 약품 주입횟수
//depth 약품을 넣는 위치
if(idx >= answer) return;
// 약품을 최솟값보다 많이 사용했다면 볼것도 없이 넘긴다.
if(depth == D){
if(isPass()) answer = Math.min(answer,idx);
return;
}
arr[depth] = -1;
dfs(depth+1,idx);
//아무것도 주입하지 않음
arr[depth] = 0;
dfs(depth+1,idx+1);
//0번 약물 주입
arr[depth] = 1;
dfs(depth+1,idx+1);
//1번 약물 주입
}
static boolean isPass(){
int[][] tmp = new int[D][W];
// 원본값을 손대면 안된다
// 검사만 하고 되돌려놓아야 하기때문에
for(int i=0;i<D;i++){
int pill = arr[i];
//한줄씩 채워진다
for(int j=0;j<W;j++){
if(pill != -1) tmp[i][j] = pill; // 주입하는 경우
else tmp[i][j] = film[i][j]; // 주입안하는 경우
}
}
// 약물 주입
int width = W;
for(int w=0;w<W;w++){
int ex = tmp[0][w]; // 첫 필름 저장
int cnt = 1;
for(int d=1;d<D;d++){
if(ex == tmp[d][w]) cnt++;
else {
cnt = 1; //ex 값이 하나 있기 때문에 1로 초기화
ex = tmp[d][w];
}
if(cnt == K) {
width--;
break;
}
}
if(width != W - (w + 1)) return false;
}
return width == 0;
}
}
정리
진짜 어려운 문제였다..
특히, 시간 복잡도 문제가 매우 컷다
if(width != W - (w + 1)) return false;이 조건문 하나로, 다음과 같은 실행시간 차이가 있었다..
여러 자료들을 찾아보았지만,이 문제의 경우 시간초과가 날 여지가 있으니. 최대한 조건을 많이 걸어서 필터링 해주라는 말 밖에 없었다.
코드를 보는데,필름검사 부분에서 전체 탐색을 하지 않는 방법이 있을까 싶어 해당 부분을 추가하게 되었다.
필름검사에서 통과하려면 두 값이 항상 똑같아야 하기때문에, 다를 경우 바로 false처리를 해주는 방식으로 해주었다.
