글 읽기 - 17136번 35%에서 자꾸 틀리네요.. 도움 요청드립니다.

ejrdnjs96 3년 전 0

알고리즘은 0,0 부터 칸이 1인지 확인하면서 1인 경우 5,4,3,2,1순으로 색종이를 붙일 수 있는 지 확인해서 붙일 수 있다면 붙여서 다시 탐색하는 방식으로 진행했습니다.

게시판이랑 예제의 반례 모두 적용해봤는데 다 통과되네요..

혹시 제가 놓친 부분이 있는지 확인 부탁 드립니다.

import java.io.*;
public class Main {
	private static int min=1001;
	public static void DFS(int map[][],int x,int y,int count[]) {
		if(over(count)) {
			return;
		}
		if(x==9 && y==9) {
			int sum=0;
			if(map[x][y]==1) {
				sum=1;
			}
			for(int i=1;i<6;i++) {
				if(count[i]>5) {
					return;
				}
				sum+=count[i];
			}
			if(min>sum) {
				int s=10;
			}
			min=Math.min(min, sum);
			return;
		}
		else {
			if(map[x][y]==0) {
				if(y==9) {
					DFS(map,x+1,0,count);
				}
				else {
					DFS(map,x,y+1,count);
				}
			}
			else {
				for(int i=5;i>0;i--) {
					if(x+i-1>=10 || y+i-1>=10) {
						continue;
					}
					if(verification(map,i,x,y)) {
						attach(i,map,count,x,y);
						if(y==9) {
							DFS(map,x+1,0,count);
						}
						else {
							DFS(map,x,y+1,count);
						}
						remove(i,map,count,x,y);
					}
				}
			}

		}
	}

	public static boolean verification(int map[][],int w,int x,int y) {
		for(int i=0;i<w;i++) {
			for(int j=0;j<w;j++) {
				if(map[x+i][y+j]==0) {
					return false;
				}
			}
		}
		return true;
	}
	public static void attach(int w,int map[][],int count[],int x,int y) {
		for(int i=0;i<w;i++) {
			for(int j=0;j<w;j++) {
				map[x+i][y+j]=0;
			}
		}
		count[w]++;
	}
	public static void remove(int w,int map[][],int count[],int x,int y) {
		for(int i=0;i<w;i++) {
			for(int j=0;j<w;j++) {
				map[x+i][y+j]=1;
			}
		}
		count[w]--;
	}
	public static boolean over(int count[]) {
		for(int i=1;i<6;i++) {
			if(count[i]>5) {
				return true;
			}
		}
		return false;
	}
	public static void main(String[] args)throws IOException{
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		int map[][]=new int[10][10];
		int count[]=new int[6];
		for(int i=0;i<10;i++) {
			String line[]=bf.readLine().split(" ");
			for(int j=0;j<10;j++) {
				map[i][j]=Integer.parseInt(line[j]);
			}
		}
		DFS(map,0,0,count);
		if(min==1001)
			min=-1;
		System.out.print(min);
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

17136번 35%에서 자꾸 틀리네요.. 도움 요청드립니다.

ejrdnjs96 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말