글 읽기 - [java]답은 맞는데 시간이 너무 차이가 납니다....

gtkim4617 4년 전 0

친구와 같은 로직인데 시간차이가 시간차이가 10배 넘게 차이가 납니다.

원인이 도대체 뭘까요? 아무리찾아도 원인을 모르겠어요 ㅠㅠ

83% 와 97%의 테스트 케이스에서 시간이 오래 걸리네요..

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	private static int[][] map;
	private static int onecnt;
	private static int correct_cnt;
	private static int min;
	private static int cnt;
	private static int[] numcnt;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		map = new int[10][10];
		onecnt = 0;

		for (int i = 0; i < 10; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < 10; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 1) {
					onecnt++;
				}
			}
		}

		numcnt = new int[5];
		for (int i = 0; i < 5; i++) {
			numcnt[i] = 5;
		}
		correct_cnt = 0;
		cnt = 0;
		min = Integer.MAX_VALUE;
		dfs(0, 0, 0);

		if (onecnt == 0) {
			System.out.println(0);
		} else if (min == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else {
			System.out.println(min);
		}

	}// end of main

	public static void dfs(int x, int y, int find_cnt) {

		if (y == 10) {
			x += 1;
			y = 0;
			dfs(x, y, find_cnt);
		}
		if (min <= cnt) {
			return;
		}
		if (correct_cnt == onecnt) {
			min = Math.min(min, cnt);
			return;
		}
		if (find_cnt == onecnt) {
			return;
		}
		if (map[x][y] > 0) {
			find_cnt++;
			if (map[x][y] == 1) {
				for (int r = 4; r >= 0; r--) {
					if (x + r < 10 && y + r < 10) {
						if (check(x, y, r) == r) {
							cnt++;
							mark(x, y, r);
							dfs(x, y + 1, find_cnt);
							cnt--;
							deletemark(x, y, r);
						}
					}
				}
			} else {
				dfs(x, y + 1, find_cnt);
			}
		} else {
			dfs(x, y + 1, find_cnt);
		}
	}

	// 길이 r만큼 체크하기
	public static int check(int x, int y, int r) {
		boolean check_size = true;
		if (numcnt[r] == 0) {
			check_size = false;
		}
		for (int i = 0; i <= r; i++) {
			for (int j = 0; j <= r; j++) {
				if (map[x + i][y + j] == 0) {
					check_size = false;
				} else if (map[x + i][y + j] == 2) {
					check_size = false;
				}
			}
		}
		if (check_size == true) {
			return r;
		} else {
			return -1;
		}
	}

	// 길이 r만큼 flag체크 하기
	public static void mark(int x, int y, int r) {
		numcnt[r]--;
		if (x + r < 10 && y + r < 10) {
			for (int i = 0; i <= r; i++) {
				for (int j = 0; j <= r; j++) {
					map[x + i][y + j] = 2;
					correct_cnt++;
				}
			}
		}
	}

	public static void deletemark(int x, int y, int r) {
		numcnt[r]++;
		if (x + r < 10 && y + r < 10) {
			for (int i = 0; i <= r; i++) {
				for (int j = 0; j <= r; j++) {
					map[x + i][y + j] = 1;
					correct_cnt--;
				}
			}
		}
	}

}

spide333 4년 전 0

저같은 경우는 dfs 함수 안에

int tp = 0;

for(int x=1;x<k;x++) tp+=5*k*k;

tp+=(5-cnt[k])*k*k;

if(ct>tp) return;

이거를 넣어줘서 앞으로 색종이를 다 써도 못 커버할 경우 dfs에서 리턴시켜줬어요

가지치기를 어디서 하고 계신가요??

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

문제

문제

출처

ICPC

[java]답은 맞는데 시간이 너무 차이가 납니다....

gtkim4617 4년 전 0

spide333 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말