글 읽기 - 14500번 테트로미노 시간초과 나는 이유가 뭘까요?

orobot 1년 전 0

완탐 가능하다고 판단해서(최악의 연산횟수 500x^2X4^4 = 2^10 x 500 = 약 2500만번) 시간적으로 충분하다고 생각하는데 계속 시간초과가 나네요.

예제 문제는 다 맞습니다.

컨셉은 T 자 모양을 제외한 테트로미노는 dfs 방식으로 탐색가능해서 dfs로 최대값 구하고 T자 모양만 따로 케이스 분류해서 최대값 구했습니다.

코드상에서 어떤 부분때문에 시간초과가 나는걸까요?

처음에 스캐너 써서 스캐너 문제이거니 해서 BR로 바꿧는데도 안되네여...

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static int N, M, MAX, map[][];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String tmp[] = br.readLine().split(" ");
		N = Integer.parseInt(tmp[0]);
		M = Integer.parseInt(tmp[1]);
		map = new int[N][M];
		for (int i = 0; i < N; i++) {
			String input[] = br.readLine().split(" ");
			for(int j = 0; j<input.length;j ++) {
				map[i][j] = Integer.parseInt(input[j]);
			}
		}
		
		MAX = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				boolean[][] visited = new boolean[N][M];
				visited[i][j] = true;
				dfs(1,i,j,visited,map[i][j]);
				makeT(i,j);
			}
		}
		
		System.out.println(MAX);
		br.close();

	}
	
	static void makeT(int x, int y) {
		int[] t = new int[4];
		if(x+1<N && y+2<M) {
			t[0] = map[x][y] + map[x][y+1] + map[x][y+2] + map[x+1][y+1];
		}
		if(x+2<N && y+1<M) {
			t[1] = map[x][y] + map[x+1][y] + map[x+1][y+1] + map[x+2][y];
		}
		if(x+2<N && y-1>=0) {
			t[2] = map[x][y] + map[x+1][y] + map[x+2][y] + map[x+1][y-1];
		}
		if(x-1>=0 && y+2<M) {
			t[3] = map[x][y] + map[x][y+1] + map[x-1][y+1] + map[x][y+2];
		}
		int tmp_max = Integer.MIN_VALUE;
		for(int sum : t) {
			tmp_max = tmp_max < sum ? sum : tmp_max;
		}
		
		MAX = MAX < tmp_max ? tmp_max : MAX;
	}
	
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,1,0,-1};
	static void dfs(int cnt, int x, int y, boolean[][] visited, int sum) {
		
		if(cnt == 4) {
			MAX = MAX < sum ? sum : MAX;
			return;
		}

		for (int d = 0; d < 4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];

			if (nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny]) continue;
			visited[nx][ny] = true;
			dfs(cnt+1,nx,ny,visited,sum+map[nx][ny]);
			visited[nx][ny] = false;
			
		}
	}
}

orobot 1년 전 0

답변감사합니다!

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

문제

문제

출처

ICPC

14500번 테트로미노 시간초과 나는 이유가 뭘까요?

orobot 1년 전 0

orobot 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말