글 읽기 - [자바]시간초과

hansorly 4년 전 0

중복을 삭제 하기 위해 Set을 썻습니다

예를들어 i=1일떄 생기는 (1,2),(1,3)( 1,4)를 Set으로 만들어 ArrayList에 넣은후

그 후에 i= 2, i= 3 , 일때 ArrayList를 검사해 (2,1) (3,1) 등은 똑같은 과정이 중복되니 중복이 되지 않게 설정했습니다 .

제가 혼자 생각하기에 발생하는 모든 중복은 없앤거 같은데 아직도 0%를 뚫지 못하고 시간초과가 납니다.

아무리 생각해도 도저히 어떤 걸 추가하고 수정해야할지 모르겠어서 질문 남깁니다 ..

import java.util.*;

public class Main {
	static int arr[][];
	static int size=0;
	static int n=0;
	static ArrayList<Integer> start=new ArrayList<Integer>();
	static ArrayList<Integer> link = new ArrayList<Integer>();
	static ArrayList<Set> a = new ArrayList<Set>();
	static int min=1000000000;
	public static void main(String[] args) {
		Scanner scanner= new Scanner(System.in);
		n= scanner.nextInt();
		arr=new int[n][n];
		size=n/2;
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				arr[i][j]=scanner.nextInt();
				}
		}
		for(int i=0;i<n;i++) {
			req(i);
		}
		System.out.println(min);
	}
	static void req(int i) {
		Set<Integer> temp = new HashSet<Integer>();
		if(start.size()==2) {
			temp.addAll(start);
			if(a.contains(temp)) {
				return;
			}
			else {
				a.add(temp);
			}
		}
		
		if(start.size()==size) {
			for(int k=0;k<n;k++) {
				if(!start.contains(k)) {
					link.add(k);
				}
			}
			min=Math.min(sum_start(),min);
			link.clear();
		}
		else {
			if(!start.contains(i)) {
				start.add(i);
				for(int k=0;k<n;k++) {
					if(!start.contains(k)) {
						req(k);
					}
				}
				
				start.remove(start.indexOf(i));
			
			}
		}
	}
	static int sum_start() {
		int sum_1=0;
		int sum_2=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++) {
				if(start.contains(i)&&start.contains(j)) {
					sum_1+=arr[i][j];
				}
				if(link.contains(i)&&link.contains(j)) {
					sum_2+=arr[i][j];
				}
			}
		}
		return Math.abs(sum_1-sum_2);
	}
	
}

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

문제

문제

출처

ICPC

[자바]시간초과

hansorly 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말