혹시나 싶어서 올려보는 질문

[세원군]

제가 요즘 한참 고민에 빠진 문제가 있어요.

사실 컴퓨터 관련이긴 한데, 한 알고리즘을 구하는거거든요.

어떤 자연수 단위 값이 직육면체의 부피로 주어졌을때, 각 변을 자연수로 고정하는 상황에서 면적을 최소로 이루는 세트를 찾는 방법인데요.

실수면 상황이 걍 세제곱근하면 깔끔하게 해결입니다.

그러나, 정수로 제한된 상황에선 이야기가 상당히 복잡해 지는데요..

세제곱근 같은건 한번에 계산하는거라 가정할때, 유한번의 과정(즉, 값에 관계없이 특정 상수번만에 해결 가능한)을 거치는 알고리즘이 어떤게 있을까요?

[비는아픔]

각 변 길이를 x,y,z라 할때 Lagrange multiplier를 통해 풀어보면 x=y=z일 때가 최소임을 알 수 있고, 따라서 이 근처에서만 조사해보면 되겠네요.
부피를 인수분해하는 알고리즘이 있으면 좀 편할거 같긴 한데,,, 만약 없으면, 그냥 노가다로...
예를들어 부피가 9이면, 9^(1/3) = 2.08... 을 우선 계산하고, 이제 이에 가장 가까운 자연수를 찾아서 9를 나눠보고(9/2), 안나눠지면 그 다음 가까운 자연수로 9를 나눠보고(9/3)... 여기서 최초로 나눠지는 자연수 x(=3)를 찾고, 그러면 9/x=3을 계산한 후, 이제 3을 yz로 나타내야 하는데 y,z가 가장 가까워야하므로, 3^(1/2)로부터 가장 가까운 자연수부터 다시 테스트하는 형식으로 해서

[세원군]

그방식.. 저도 생각했다만.. 슬프게도, 소인수가 3개인데 작은 소인수 2개의 곱이 세제곱근과 유사할때, 문제가 됩니다. 예를들면 23*2*3=138인데, 가장 근처에 있는 숫자 5부터 계산하면, 6이 걸러져버리는데, 그건 안되죠..

[비는아픔]

그렇네요... 위와같이 하려면 나눈 후의 숫자를 고려해야된다는 뜻인데,,, 어렵네요 ㅠㅠ 그나마 생각나는건, 걸러지는 숫자가 아예 세제곱근 자체이면 OK, 세제곱근이 아니더라도 소수이면 OK이고, 소수가 아니면 그 숫자를 소인수분해해서, 몫에 하나씩 보내서 테스트하는 방법인데 숫자가 크면 시간이 상당히 걸릴듯...; 그래도 다 테스트하는거보다 낫긴 한데 더 좋은방법은... 생각해봐야겠네요... 근데 무엇때문에 이게 필요하신거죠?

[세원군]

그냥.. 개인적으로 알고리즘 이용해서 문제푸는 사이트에서 나온 문제라서요 ㅋㅋ

아마 그 문제는 다 돌려보는걸 생각하는거 같은데

좀 깔끔한게 없나 생각하고 있거든요 ㅋㅋ

[비는아픔]

x=y=3, z=1를 얻습니다. 100% 다 되는지는 잘 모르겠네요ㅠ