인프런 커뮤니티 질문&답변
작성한 질문수
결국 dy값을 없데이트 해나가는 동전의 순서는 상관이 없는 것이죠?
작성
·
233
1
안녕하세요, 선생님! 강의 잘 듣고 있습니다! 이 문제는 "거슬러주는 값을 0 부터 15 까지 dy 인덱스로 배열하고 그 각각에 대하여 동전들을 차례대로 적용하여 제일 좋은 값 (최소개수)를 찾아간다" 이렇게 이해를 했는데요. 결국 적용하는 동전의 순서는 상관이 없는것이죠? (1, 2, 5) 로 하나 (5, 2, 1) 또는 (2, 5, 1) 로 하나 답이 같게 나오는데 직관적으로는 알겠는데 왜 순서가 상관없는지 이해하려니 조금 헷갈립니다 ㅠㅠ
답변 1
1
김태원
지식공유자
안녕하세요^^
적용하는 동전의 순서를 상관없습니다. 매번 적용할 때 기존경우보다 더 좋으면 dy의 값은 바뀌게 되어 있으면 최종적으로는 모든 동전을 적용했을 때 최적의 값만 dy에 남아 있게 됩니다.
적용되는 순서는 상관없고, 모든 동전을 적용만 하면 됩니다.