cod2dev   2년 전

재귀호출 문제 중 쉽고 간단한 문제를 고른건데도 불구하고 못풀어서 부탁드려요ㅠㅠ


제가 하려고 한 건 문제에 대해 완전탐색을 재귀호출로 구현하려했습니다.

pick함수가 diff를 반환하지도 않는데 min함수로 현재 함수의 diff랑 비교하고.. 제가 봐도 안돌아가게 짰지만

재귀함수에 대한 이해도가 낮아서, 어디를 바꿔야 할 지 모르겠습니다.

도움 부탁드려요.

chogahui05   2년 전

이 문제 생각보다 어렵지요?

제일 쉬운 방법은 log10 함수를 써서, 가망성이 없는 경우 빠르게 잘라내 버리는 것입니다.

가망성이 없다는 것은 이미 신 맛이라는 수치가 굉장히 커져버려서 쓴맛으로 차이를 보정한다고 해도 도저히 안 되는 경우를 말합니다.


예를 들어서 여태까지 계산한 신맛들의 곱을 t, 쓴 맛들의 합을 p라고 해 봅시다.

여기서, 신맛 t'과 p'이 들어왔습니다. 이 경우


tt' - (p + p') 은 어떻게 구하죠?

t가 10의 17승, 20승보다 커졌다고 가정해 봅시다.

p나 p'은 많아봤자 10억이죠.

tt'은 10의 17승, 20승보다 큽니다. 여기서 10억을 빼 봤자 얼마나 빠질까요?


만약에 신맛들의 곱 한계치를 40억? 50억? 정도로 설정했다고 해 봅시다.

이 경우는 10억, 20억이 빠지는 게 꽤 크리티컬해집니다.

하지만 10의 17승에 비해서 10억, 20억은 그냥 작은 숫자일 뿐이지요.


chogahui05   2년 전

log(a*b) = loga + logb 이고요.

10진수 x의 자릿수는 logx의 정수부라는 것을 생각하신다면. 제가 말한 것은

매우 쉽게 구현 가능하십니다. 2^63은 대충. 18자리 정도가 나오고요. 오버플로우가 나지 않게 하기 위해서

log10(재료들을 곱한 값들) 의 리턴값이 17 이상이면 가망성이 없다고 판단하고 계산하지 않는다면 답이 나올 거 같네요.


물어보는 것은 기초적인 재귀인데요. 약간의 수학적인 분석력도 필요하지 않았나 싶네요.

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