kisrin4319   4년 전

아직 dp로 코드 짜는 법을 제대로 알지 못해서 일단 brute force 식으로 짜본 코드입니다.

sqrt를 활용해 최대 제곱수에 가깝게 만든 후 숫자를 줄여나면서 최소항 갯수를 구하는 식으로 구현해봤습니다.

테스트 케이스랑 몇개는 되는것 같은데 오답 처리가 되어 이렇게 질문 드립니다.

cozyyg   4년 전

때로는 최대 제곱수에 가깝게 만드는 것이 최선이 아닐 때가 있습니다.

12=9+1+1+1이 되지만 12=4+4+4로 하면 더 적은 개수로 할 수 있습니다.

32=25+4+1+1+1보다 32=16+16이 더 개수가 적습니다.

https://www.acmicpc.net/proble...

동전 교환 알고리즘(Coin Change)을 구글링해서 찾아보면 도움이 될 수도 있습니다.

kisrin4319   4년 전

위 제 코드를 실행 시켰을 시에 min = 2로 나오게 구현되어있습니다.

물론 12를 넣었을 경우에도 min=3 으로 출력이 되는데 최대 제곱수에 가깝게 만드는것 부터 잘못일까요?

cozyyg   4년 전

아 반례 찾기 어렵네요...

43=25+9+9에서 43에는 3이 나와야 합니다.

저 코드에서는 4가 나옵니다.

12나 32 같은 경우에는 첫 번째 수를 잘 잡으면 그 다음부터는 최대 제곱수를 잡아도 되지만, 43의 경우 저 코드에서는 25 다음에 16을 택하게 되어 최소인 25,9,9를 찾을 수 없습니다. brute force로 구현하기는 좀 어려운 문제일 듯 합니다.

kisrin4319   4년 전

도움 주셔서 감사합니다!

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