글 읽기 - 시간초과 질문이요~

sksdong1 7년 전 0

알고리즘은 입력된 단어 전부 때려박고

각 단어에 순서를 강제해서 picked 벡터에 넣구요

맨 앞에서부터 9점 이후로 1점씩 떨어지게 해서 완전탐색으로 짯는데

보통 완전탐색이였으면 패스됬을텐데 max값 계산하는 부분이 문제 같은데

어떻게 해야 할까요?

import java.util.Scanner;
import java.util.Vector;

class Main{
	
	static Vector<Integer> picked = new Vector<Integer>();
	static Vector<Integer> vec = new Vector<Integer>();
	static String[] str;
	static int[] value = new int[26];
	static int k,max;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		k = sc.nextInt();
		str = new String[k];
			
		for(int i=0;i<k;i++){
			str[i] = sc.next();
			for(int j=0;j<str[i].length();j++){
				if(!vec.contains(str[i].charAt(j)-'A')){
					vec.add(str[i].charAt(j)-'A');
				}
			}
		}
		boolean used[] = new boolean[10];
		find(picked,vec.size(),used);
		System.out.println(max);
	}
	public static void find(Vector<Integer> picked,int toPick,boolean[] used){
		if(toPick==0){
			int sum = 0;
			for(int i=0;i<k;i++){
				sum += change(str[i]);
			}
			max = max>sum?max:sum;
		}
		
		for(int i=0;i<vec.size();i++){
			int here = vec.get(i);
			if(used[i]) continue;
			picked.add(here);
			used[i]=true;
			find(picked,toPick-1,used);
			used[i]=false;
			picked.remove(picked.lastElement());
		}
		
	}
	public static int change(String str){
		int value = 0;
		int cipher=1;
		for(int i=str.length()-1;i>=0;i--){
			value += (9 - picked.indexOf(str.charAt(i)-'A')) * cipher;
			cipher*=10;
		}
	
		return value;
	}
}

zlzmsrhak 7년 전 0

topick가 0일 때 함수를 끝내지 않아서 시간초과가 나는 것이 아닐까요

sksdong1 7년 전 0

return 추가해도 똑같네요. 음..

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

문제

문제

출처

ICPC

시간초과 질문이요~

sksdong1 7년 전 0

zlzmsrhak 7년 전 0

sksdong1 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말