코딩테스트
-
[자료구조] [python] [Dynamic Programming] The Coin Change ProblemData miner/Algorithm & Data structure 2022. 2. 8. 20:15
Hackerrank의 Data structures 관한 문제 중에서 Algorithms에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/coin-change/problem?isFullScreen=true 문제를 푸는 아이디어를 떠올리는 것은 어렵지 않다. Coins 리스트에서 앞의 원소의 코인부터 시작해서 무제한으로 제공되는 코인을 통해 가능한 금액의 경우의 수를 구하고, 이후 인덱스의 코인들의 조합을 통해 가능한 금액을 업데이트 하는 식으로 구하면 된다. 하지만, 실제 이를 코드로 구현하는 과정에서 시간이 소요되었다. 실제 풀이한 코드 방법은 다음과 같다. 문제에서 주어진 우리가 만들어야 하는 금액이 n이고, Coins 리스트에..