2293번 - 동전 1
https://www.acmicpc.net/board/...
오답이 떴길래 링크의 데이터를 참조하다 못해 정답인 코드랑 거의 똑같이 쓰다시피 했는데
answer : 2013845695 now : 2146712920
"분명 메모이제이션한 최대 값이 곧 경우의 수일 것이라 생각하고"
이 문장에 대한 간단한 반례입니다. 동전이 2원짜리 한 종류만 있을 때, 9원을 만드는 경우의 수가 많을까요, 8원을 만드는 경우의 수가 많을까요?
ㄴ 그런 크리티컬한 케이스를 미처 생각해내지 못했군요...
좋은 반례 제공해주셔서 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
herdson 4년 전
https://www.acmicpc.net/board/...
오답이 떴길래 링크의 데이터를 참조하다 못해 정답인 코드랑 거의 똑같이 쓰다시피 했는데
계속 이렇게 나오는 겁니다...그래서 답 출력을 dp 배열[만들어야 하는 가치 값] 으로 바꿨더니 멀쩡하게 나왔습니다.
분명 메모이제이션한 최대 값이 곧 경우의 수일 것이라 생각하고 max_element를 사용했던 것이었는데 오답을 만드는 결정적 요인이 되었던 것 같습니다.
왜 이런 결과가 나온 것일까요??