글 읽기 - (자바)샘플 답은 제대로 나오는데 왜 틀린걸까요

wan088 5년 전 0

제가 푼 방식은 우선 배열 내의 숫자들을 모드 소팅했구요.

a1, a2, ........an까지 오름차순으로 소팅되었다고 할때

마지막 합성할때 곱해지는 비용은 a1*a2*......*an으로 고정되므로 그전 단계를 최소화하는 방향으로 재귀적으로 구성했습니다.

이 때 마지막 합성 직전단계에서 전체를 두 집단으로 나누는 경우는 nC2겠지만 오름차순으로 정렬했을때는 크기가 큰 집단에 낮은 숫자들을 모두 집어넣을때 최소값이 나오므로

n가지 경우로 다음과 같이 코딩했습니다.

이부분에선 제 추측이랑 개인적인 계산이 들어갔지만 샘플들을 몇개 더 추가했을때도 문제없었는데 뭐가 문제일까요?

혹시 틀렸다면 어떤식으로 개선해야할지 조언 부탁드립니다. ㅠㅠ

import java.util.Arrays;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		
		try{
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		int sn;
		int[] slime;
		
		for(int i =0 ; i<t ; i++){
			sn=sc.nextInt();
			slime= new int[sn];
			for(int j = 0 ; j<sn ; j++){
				slime[j]=sc.nextInt();
			}
			Arrays.sort(slime);
			
			System.out.println(Slime(slime, 0, sn-1)%1000000007);
			
			
		}
		
		sc.close();
		}catch(Exception e){
			System.out.println();
		}
	}
	
	
	static int Slime(int[] arr, int left, int right){
		int leng=0; int answer=0;
		if(left==right)
			return 1;
		else{
			leng=right-left+1;
			answer=Slime(arr, left, left)*Slime(arr, left+1 , right);
			for(int i=1 ; i<leng-1 ; i++){
				if(Slime(arr, left, left+i)*Slime(arr, left+i+1 , right)<answer)
					answer=Slime(arr, left, left+i)*Slime(arr, left+i+1 , right);
			}
			
			for(int j=left ; j<=right ; j++)
				answer*=arr[j];
			
			return answer;
			
		}
	}
	

}

jh05013 5년 전 1

오버플로우가 납니다.

1
2
1500000000 2

wan088 5년 전 0

@jh05013

답변 감사합니다 근데 덕분에 오버플로우 문제는 해결했는데 그래도 틀렸다고 계속 나오네요.

혹시 문제푸는 방향이 잘못됐던건가요?

jh05013 5년 전 1

오버플로우가 아직 해결되지 않았습니다. 슬라임의 에너지는 long long 범위에 있지만, 비용은 long long을 초과할 수 있습니다.

그래서 Slime(arr, left, left)*Slime(arr, left+1 , right)%1000000007 같은 식으로 계산 과정마다 1000000007로 나눠 줘야 오버플로우를 피할 수 있는데, 문제는 이러면 어느 값이 더 큰 지 알 수 없어서... 풀이가 맞다면 BigInteger를 써서 해결할 수 있을 것 같습니다.

1
4
100000 1000000 10000000 2

wan088 5년 전 0

@jh05013

BigInteger라는 것도 있는지 처음알았습니다.;ㅎㅎ 말씀하신대로 계산과정마다 나눠주는건 불가능했고 BigInteger로 해야 그나마 답이 나오는 것 같습니다.

하지만 이 경우에 채점에선 시간초과가 떠버리네요;;

아예 다른 방법으로 이런저런 시도를 해봤는데 도저히 잘 안되서 나중에 머리식히고 다시 풀어봐야 할 것 같습니다.

덕분에 많은 도움 됐습니다. 감사합니다!

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

문제

문제

출처

ICPC

(자바)샘플 답은 제대로 나오는데 왜 틀린걸까요

wan088 5년 전 0

jh05013 5년 전 1

wan088 5년 전 0

jh05013 5년 전 1

wan088 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말