글 읽기 - [자바] 다른 정답코드와 다른점이 무엇인지 모르겠는데 자꾸 시간초과가 납니다.

zxc2346 2년 전 0

원인이 뭘까요...하...

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

public class Main {

	static int n;
	static int arr[][];
	static int used[];
	static int red;
	static int blue;
	static int answer = Integer.MAX_VALUE;
	
	static void rec1(int depth, int k) {
		if(depth == n/2) {
			red = 0;
			blue = 0;
			for(int i = 0 ; i < n-1 ; i++) {
				for(int j = i+1 ; j < n ; j++) {
					if(used[i] == 1 && used[j] == 1) {
						red += arr[i][j] + arr[j][i];
					}
					if(used[i] == 0 && used[j] == 0) {
						blue += arr[i][j] + arr[j][i];
					}
				}
			}
			answer = Math.min(answer, Math.abs(red- blue));
			//System.out.println(red);
		}else {
			for(int i = k ; i < n ; i++) {
				if(used[i] == 1) {
					continue;
				}
				used[i] = 1;
				rec1(depth+1, k+1);
				used[i] = 0;
			}
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new int[n][n];
		used = new int[n];
		StringTokenizer st;
		for(int i = 0 ; i < n ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < n ; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		rec1(0,0);
		System.out.println(answer);
		
		
	}

}

projung0722 2년 전 3

팀을 뽑을때 1-2-3 을 뽑는것과 1-3-2 또는 3-1-2 뽑는것이 같습니다. 이같은경우가 생기면 같은 팀구성인 경우를 몇번씩 다시 계산하며 반복문이 여러번 돌게 됩니다.

따라서 그 부분을 줄여주도록 순열이 아니라 조합을 사용해서 팀을 뽑아 주는것이 좋습니다. 오름차순인 순열을 생각하시면 될 것 같습니다. 알고계셨던걸수도있는데 코드에서 보면

for(int i = k ; i < n ; i++) 이부분에서 k가 전에 고른 팀원번호 (전에사용한 i) 가되도록 바꿔주시면 될것같아요.

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

문제

문제

출처

ICPC

[자바] 다른 정답코드와 다른점이 무엇인지 모르겠는데 자꾸 시간초과가 납니다.

zxc2346 2년 전 0

projung0722 2년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말