글 읽기 - 시간초과가 납니다.

nhe1229 7년 전 0

답은 맞는데 시간초과가 납니다.

어디가 잘못된건지 모르겠어요

package hw;

import java.io.FileInputStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class meetingRoom {
	static int [][] Mat;
	static int [] visited;
	static int maxDepth, depth;
	static int N, roomCnt, maxRoomCnt, totalCnt, bCnt,aCnt,CNT;
	static int [] cntArray;
	
	public static void dfs(int vertex, int cnt){
		
		if (cnt > maxRoomCnt) {
			maxRoomCnt = cnt;
			return;
		}
		
		if(vertex == N-1){
			return;
		}
			
		for(int i=vertex; i<N; i++){
			if(visited[i] == 0 && Mat[i][0] >= Mat[vertex][1] ) 
			{
			visited[i]=1;		
			dfs(i, cnt+1);
			visited[i]=0;
			}
		}
	}
	
	
	public static void main(String[] args) throws Exception{

		System.setIn(new FileInputStream("C:\\inputSamples\\sample_input_meetingRoom.txt"));

		Scanner sc = new Scanner(System.in);
			
		N = sc.nextInt();
		maxRoomCnt =0;
		Mat = new int [N][2];
		visited = new int [N];
		
		for(int i=0; i<N; i++){
			Mat[i][0] = sc.nextInt();
			Mat[i][1] = sc.nextInt();		
			//System.out.print(Mat[i][0] + " , " + Mat[i][1]);
			//System.out.println();
		}
		
		Arrays.sort(Mat, 0, N, new Comparator<int[]>() {//7. 회의의 유효여부를 체크할 때에 시작시간으로 정렬이 되어 있으면 편하기 때문에 정렬을 먼저 해놓는다.
			public int compare(int[]p1, int[]p2) {
				return p1[0]-p2[0];
			}
		});		

		
		//roof안돌려도 되나 ? 
		for(int i=0; i<4; i++){   
			visited[i] = 1;
			dfs(Mat[i][0], 1);
		}
		
		System.out.println(maxRoomCnt);
	}
	
	
}

hihihi 7년 전 0

이 코드 복잡도는 O(N^N) 인 것 같아요

근데 n제한이 10만이라 시간초과가 납니다

알고리즘 수정이 필요합니닷

aod0326 7년 전 0

그리디 알고리즘 특성을 활용하면

코드 길이도 확 줄고

O(nlgn)정도로 끝낼 수 있어요 ㅎㅎ

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

문제

문제

출처

ICPC

시간초과가 납니다.

nhe1229 7년 전 0

hihihi 7년 전 0

aod0326 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말