SWEA 보호필름
구현전 생각
먼저 모든 조건에 대해서 시도 해보는 완전 탐색으로 생각.
DFS를 이용해서 해당 행에 약품을 넣을지 안넣을지로 나누어서 재귀를 이용한 탐색을 한다.
아쉬운점
기저 조건 순서를 잘 생각하여 배치하자
코드
package backjoon_4월;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class SWEA_보호필름 {
static int map[][];
static int N,M,K;
static int min;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int TC = Integer.parseInt(br.readLine());
for (int t = 1; t <= TC; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
min = Integer.MAX_VALUE;
map= new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j]=Integer.parseInt(st.nextToken());
}
}
findmin(0,0);
System.out.println("#"+t+" "+min);
}
}
private static void findmin(int x,int cnt) {
if(cnt >= min ) return;
if(check()) {
min = Math.min(min, cnt);
return;
}
if(x== N) return;
int [] before = map[x].clone();
//약품 삽입 x
findmin(x+1,cnt);
//A 약품
Arrays.fill(map[x],0);
findmin(x+1,cnt+1);
//B약품
Arrays.fill(map[x],1);
findmin(x+1,cnt+1);
map[x]=before;
}
private static boolean check() {
//각 열을 k만큼 깊이 들어가서 확인
for (int i = 0; i <M; i++) {
int cnt = 0;
boolean flag = true;
int before=map[0][i];
for (int j = 0; j < N; j++) {
if(before==map[j][i]) {
cnt++;
if(cnt==K) {
flag =false;
break;
}
}
else {
before = map[j][i];
cnt=1;
}
}
if(flag) return false;
}
return true;
}
}
Author And Source
이 문제에 관하여(SWEA 보호필름), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jeus95/SWEA-보호필름저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)