jupiny   4년 전

다이나믹 프로그래밍을 이용해 풀었는데, 계속 45%에서 에러가 발생하네요 ㅠㅠ

남아있는 추를 모두 사용해도 절대 구슬의 무게를 만들 수 없을 때는 false를 반환하도록 예외처리를 하였는데 어떤 반례가 있는 걸까요??


답변주시면 감사하겠습니다! 


dp(idx, state): weight[idx]에서 weight[n-1] 까지의 추를 이용하여 state 값을 만들 수 있는지의 여부를 반환하는 함수

ho94949   4년 전

18-19번째 라인을 유심히 보시기 바랍니다.
과연 현재까지의 무게의 합이 음수라고 해서, 전체 원하는 무게를 만들지 못할까요?

jupiny   4년 전

아 제가 잘못 생각하고 있었네요 ㅠㅠㅠ

제가 생각한 알고리즘을 제가 잘못 이해하고 있었네요.

말씀해주신대로 18-19번째 줄 코드를 제거하고 14번째 줄 코드에도 음수 최솟값에 대한 조건을 추가하였더니 바로 해결됬어요!

정말 감사드립니다 :D

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