kioio5   2년 전

이 코드가 틀린이유가뭘까요??? 결과는 잘 나오는것 같은데요..

chogahui05   2년 전

dp[i] = dp[k*k] + dp[i-k*k]라..

k야 sqrt해서 나오는 것일 테고.. i 이하인 가장 큰 제곱수를 택한다는 그리디 전략이 아닌가요?

사실 반례가 있죠.

32

답 : 16 + 16


님이 선택하는 전략에 따르면

32 = 25 + 7

= 25 + 4 + 3

= 25 + 4 + 1 + 1 + 1

이렇게 됩니다.

chogahui05   2년 전

그리고.. sqrt 함수를 호출할 필요가 있을지는 모르겠습니다만.. 비용이 그렇게 많이 드는 것도 아니고..

i*i <= j 조건을 (돌 때마다) 검사할 바에야. sqrt를 한 번 정도 호출해 줘서 i <= k 조건으로 단순화 시키는 것도

나쁘지 않은 생각인 거 같네요.

kioio5   2년 전

와우..... 반례 정말 감사합니다 !!

고맙습니다!!!!!

!_!

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