PROBLEM
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
LOGIC
- 나올 수 있는 모든 경우의 부분집합을 구한다
- 약품 처리를 하는 경우
- 약품A를 처리하는 경우
- 약품B를 처리하는 경우
- 완성된 부분집합마다 성능 검사를 한다
CODE
package SWEA2112;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int film[][];
static int thickness,width,passLimit;
static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws NumberFormatException, IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int T = Integer.parseInt(br.readLine());
for(int tc = 1; tc<=T; tc++)
{
st = new StringTokenizer(br.readLine());
thickness = Integer.parseInt(st.nextToken());//보호 필름의 두께 D
width = Integer.parseInt(st.nextToken());//가로 크기 W
passLimit = Integer.parseInt(st.nextToken());//합격 기준 K
answer = Integer.MAX_VALUE;
film = new int[thickness][width];
for(int i = 0; i<thickness; i++)
{
st = new StringTokenizer(br.readLine());
for(int j = 0; j<width; j++)
{
film[i][j] = Integer.parseInt(st.nextToken());
}
}
subset(0,0);
System.out.println("#"+tc+" "+answer);
}
}
private static void subset(int cnt, int index)
{
if(cnt>=answer)
{
return;
}
if(index == thickness)
{
if(check())//검사에 통과 했다면
{
answer = cnt;
}
return;
}
int saveBefore[] = film[index].clone();
subset(cnt, index+1);//약품 처리하지 않는 경우
useChemical(index, 0);
subset(cnt+1,index+1);//약품 A를 처리하는 경우
useChemical(index, 1);
subset(cnt+1,index+1);//약품 B를 처리하는 경우
film[index] = saveBefore;//약품 처리 전으로 되돌리기
}
private static boolean check()
{
int count, type;
boolean isEqual = false;
for(int i = 0; i<width; i++)
{
count = 1;
type = film[0][i];
isEqual = false;
for(int j = 1; j<thickness; j++)
{
if(type == film[j][i])
{
count++;
}
else
{
type = film[j][i];
count = 1;
}
if(count == passLimit)
{
isEqual = true;
break;
}
}
if(!isEqual) return false;
}
return true;
}
private static void useChemical(int row, int chemical)
{
for(int i = 0; i<width; i++)
{
film[row][i] = chemical;
}
}
}