인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

인프런 커뮤니티 질문&답변

민수 S님의 프로필 이미지
민수 S

작성한 질문수

자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)

4. 동전교환(냅색 알고리즘)

결국 dy값을 없데이트 해나가는 동전의 순서는 상관이 없는 것이죠?

작성

·

233

1

안녕하세요, 선생님! 강의 잘 듣고 있습니다!  이 문제는 "거슬러주는 값을 0 부터 15 까지 dy 인덱스로 배열하고 그 각각에 대하여 동전들을 차례대로 적용하여 제일 좋은 값 (최소개수)를 찾아간다" 이렇게 이해를 했는데요. 결국 적용하는 동전의 순서는 상관이 없는것이죠? (1, 2, 5) 로 하나 (5, 2, 1) 또는  (2, 5, 1) 로 하나 답이 같게 나오는데 직관적으로는 알겠는데 왜 순서가 상관없는지 이해하려니 조금 헷갈립니다 ㅠㅠ

답변 1

1

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

적용하는 동전의 순서를 상관없습니다. 매번 적용할 때 기존경우보다 더 좋으면 dy의 값은 바뀌게 되어 있으면 최종적으로는 모든 동전을 적용했을 때 최적의 값만 dy에 남아 있게 됩니다.

적용되는 순서는 상관없고, 모든 동전을 적용만 하면 됩니다.

민수 S님의 프로필 이미지
민수 S

작성한 질문수

질문하기