글 읽기 - 시간초과 어떻게 해결할 수 있을까요?

ljs921026 4년 전 0

차례로 돌아가면서 색종이 붙였다 뗐다 하는 과정 반복하면서

최소값 찾도록 완전탐색 구현했습니다.

어디부분에서 더 가지치기를 쳐야 될까요?

import java.util.*;
import java.io.*;

public class Main {
	public static int[] use;
	public static int remain;
	public static int min;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int[][] map=new int[10][10];
		int y=-1;
		remain=0;
		for(int i=0;i<10;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<10;j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
				if(map[i][j]==1) {
					if(y==-1) {
						y=i;
					}
					remain++;
				}
			}
		}
		
		use=new int[6];
		Arrays.fill(use, 5);
		min=987654321;
		
		if(y==-1)
			System.out.println(0);
		else {
			int result=getMin(map,y,0,0);
			if(result==987654321)
				System.out.println(-1);
			else
				System.out.println(result);
		}
	}
	
	//y,x를 왼쪽위 모서리로 해서 색종이를 붙임
	public static int getMin(int[][] map,int y,int erase,int cnt) {
		if(min<=cnt)
			return 987654321;
		if(erase==remain) {
			min=Math.min(min, cnt);
			return cnt;
		}
		
		int result=987654321;
		int[][] mapCopy=deepCopy(map);
		
		for(int i=y;i<10;i++) {
			for(int j=0;j<10;j++) {
				if(mapCopy[i][j]==1) {
					boolean flag=false;
					for(int size=5;size>=0;size--) {
						if(!flag&&use[size]>0&&check(mapCopy,i,j,size)) {
							flag=true;
							use[size]--;
							result=Math.min(result, getMin(mapCopy,i,(int) (erase+Math.pow(size, 2)),cnt+1));
							mapCopy=deepCopy(map);
							use[size]++;
						}
					}
					if(!flag)
						return 987654321;
				}
			}
		}		
		
		return result;
	}
	
	public static boolean check(int[][] map,int y,int x,int size) {
		//색종이 붙일 수 있는지 확인
		boolean result=true;
		for(int i=y;i<y+size;i++) {
			for(int j=x;j<x+size;j++) {
				if(i>=10||j>=10||map[i][j]==0)
					return false;
			}
		}
		
		//붙일 수 있으면 붙이기
		if(result) {
			for(int i=y;i<y+size;i++) {
				for(int j=x;j<x+size;j++) {
					map[i][j]=0;
				}
			}
		}
		
		return result;
	}
	
	public static int[][] deepCopy(int[][] original){
		int[][] copy=new int[10][10];
		for(int i=0;i<10;i++)
			System.arraycopy(original[i], 0, copy[i], 0, 10);
		
		return copy;
	}
}

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

문제

문제

출처

ICPC

시간초과 어떻게 해결할 수 있을까요?

ljs921026 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말