글 읽기 - 자바 시간초과가 나는 이유를 잘 모르겠습니다.

cleankid99 3년 전 0

알고리즘은 다른분들과 같게 조합으로 풀었습니다만...

왜 채점이 0%부터 시간초과가 나는지 이유를 도통 모르겠습니다ㅠㅠ

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

public class Main {

	static int[][] map;
	static boolean[] chk;
	static int min = 999999;
	static int n;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		
		map = new int[n+1][n+1];
		chk = new boolean[n+1];
		
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=1; j<=n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		solve(1,0);
		
		System.out.println(min);
	}
	
	public static void solve(int start, int cnt) { // 조합 사용
		if(cnt == n/2) {
			// start팀과 link팀의 차이값 구해서 최소값 갱신
			
			int sum_start=0;
			int sum_link=0;
			
			for(int i=1; i<=n; i++) {
				for(int j=1; j<=n; j++) {
					if(chk[i] && chk[j]) { // start팀
						sum_start += map[i][j];
					}
					
					if(!chk[i] && !chk[j]) { // link팀
						sum_link += map[i][j];
					}
					
				}
			}
			
			int result = Math.abs(sum_start-sum_link);
			
			if(min > result) {
				min = result;
			}
			
			return;
		}
		
		for(int i=start; i<=n; i++) {
			if(!chk[i]) {
				chk[i]=true;
				solve(start+1, cnt+1);
				chk[i]=false;
			}
		}
		
		return;
	}

}

heize 3년 전 2

http://boj.kr/84997b1d3a904d4d...

조합으로 구현하셨다면, 66번째 start + 1이 아니라 i + 1이 아닐까요?

i + 1로 바꾸어서 위 소스처럼 AC를 받았습니다.

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

문제

문제

출처

ICPC

자바 시간초과가 나는 이유를 잘 모르겠습니다.

cleankid99 3년 전 0

heize 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말