글 읽기 - 시간초과 가지치기 도움좀 부탁드립니다.

le_effort 4년 전 0

어느 조건을 추가해야 시간초과가 안날지 전혀 모르겠습니다 ㅠ

도움좀 부탁드릴게요...

import java.io.*;
import java.util.*;
public class Main {
	static int[] color_paper = {0,5,5,5,5,5};
	static int arr[][];
	static int ans=Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int one=0;
		arr = new int[10][10];
		for(int i=0; i<10; i++) {
			String[] t = br.readLine().split(" ");
			for(int j=0; j<10; j++) {
				arr[i][j]=Integer.parseInt(t[j]);
				if(arr[i][j]==1) {
					one++;
				}
			}
		}
	
		dfs(0,0,one);
		if(ans==Integer.MAX_VALUE) {
			System.out.println(-1);
		}
		else {
			System.out.println(ans);
		}
	}
	public static void dfs(int r, int cnt, int one_cnt) {
		//System.out.println(one_cnt);
		if(cnt>=ans) {
			return ;
		}
		if(one_cnt ==0) {
			ans = Math.min(ans, cnt);
			return ;
		}
		for(int i=r; i<10; i++) {
			for(int j=0; j<10; j++) {
				if(arr[i][j]==1) {
					boolean bl = false;
					for(int k=5; k>0; k--) {
						if(i+k <=10 && j+k<=10 && color_paper[k]>=0) {
							if(!bl) {
								if(check(i,j,k)) {
									bl = true;
									fill(i,j,k,0);
									color_paper[k]--;
									dfs(r,cnt+1,one_cnt-k*k);
									fill(i,j,k,1);
									color_paper[k]++;
								}
							}
						}
					}
				}
			}
		}
	}
	public static boolean check(int a, int b, int size) {
		for(int i = a; i<a+size; i++) {
			for(int j=b; j<b+size; j++) {
				if(arr[i][j]==0) {
					return false;
				}
			}
		}
		return true;
	}
	public static void fill(int r, int c, int size,int state) {
		for(int i=r; i<r+size; i++) {
			for(int j=c; j<c+size; j++) {
				arr[i][j]=state;
			}
		}
	}
}

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

문제

문제

출처

ICPC

시간초과 가지치기 도움좀 부탁드립니다.

le_effort 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말