rlejr135   2년 전

주석은 확인좀 하려고 달아둔거니 무시해주시고..

dy에다 1층 사면체에는 1개가 필요하고, 2층 사면체에는 4개가 필요하고, 3층에는 10개.. 이런 식으로 저장한 후

 n개의 대포알로 가장 크게 만들 수 있는 사면체부터 만들며 대포알 숫자를 점점 줄여나갔는데

다른 예가 있나요? 아니면 제가 문제 자체를 잘못 이해한 건가요?

lll4592   2년 전

동전 문제와 유형이 같습니다. 1원 5원 11원이 있을때 큰거부터 주면 답이 5이지만 5원을 3개 를 주는 더 최적인 경우가 존재하죠. 따라서 이 문제는 그리디 알고리즘이 아닌 다이나믹 프로그래밍으로 문제를 해결해야 합니다.

kesakiyo   2년 전

소스를 보면 현재 가지고 있는 대포알에서 

만들 수 있는 가장 큰 사면체 모양의 대포알만큼 빼는 코드를 작성하셨네요.

이러한 그리디 방식으로는 문제에서 요구하는 답을 구하지 못해요.

파워 반례를 들자면 인풋이 40이라고 할 때 rlejr135님의 코드는 

만들 수 있는 사면체의 최소 수가 3이라고 답을 합니다.

하지만 20개의 대포알을 사용하는 4층짜리 사면체 두개로 40개를 모두 사용할 수 있습니다.

때문에 답은 2가 되어야 하죠.

rlejr135   2년 전

아 그렇구나

감사합니다!

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