wan088   6년 전

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

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

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

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

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

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

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



jh05013   6년 전

오버플로우가 납니다.

wan088   6년 전

@jh05013

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

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

jh05013   6년 전

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

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

wan088   6년 전

@jh05013

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

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

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

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

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