-
[자료구조] [python] [Dynamic Programming] The Coin Change ProblemData miner/Algorithm & Data structure 2022. 2. 8. 20:15728x90
Hackerrank의 Data structures 관한 문제 중에서 Algorithms에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자.
https://www.hackerrank.com/challenges/coin-change/problem?isFullScreen=true문제를 푸는 아이디어를 떠올리는 것은 어렵지 않다. Coins 리스트에서 앞의 원소의 코인부터 시작해서 무제한으로 제공되는 코인을 통해 가능한 금액의 경우의 수를 구하고, 이후 인덱스의 코인들의 조합을 통해 가능한 금액을 업데이트 하는 식으로 구하면 된다.
하지만, 실제 이를 코드로 구현하는 과정에서 시간이 소요되었다.
실제 풀이한 코드 방법은 다음과 같다.
문제에서 주어진 우리가 만들어야 하는 금액이 n이고, Coins 리스트에 들어간 샘플 코인이 coin이라고 하자.
먼저, 0~n까지 금액을 만들 수 있는 코인의 조합 경우의 수를 담은 메모라이즈할 수 있는 리스트를 만든다.
이 리스트의 인덱스의 위치는 금액을 뜻하며, 인덱스 원소의 값은 금액을 구성하는 코인의 조합 경우의 수를 뜻한다.
금액이 0인 경우를 1로 만들어, 추후에 코인 자기 자신 하나의 경우의 수를 업데이트할 때 +1할 수 있도록 만든다.
주어진 코인 리스트에서 차례대로 코인들을 꺼내어 1부터 n까지 가능한 금액의 수를 차례차례 업데이트한다.
> n_lists[i] = n_lists[i] + n_lists[i-coin]
def getWays(n, c): # Write your code here n_lists = [0 for i in range(n+1)] n_lists[0] = 1 for coin in c: if n >= coin: for i in range(1, n+1): if i-coin >= 0: n_lists[i] = n_lists[i] + n_lists[i-coin] return n_lists[n]
'Data miner > Algorithm & Data structure' 카테고리의 다른 글
[자료구조] [python] [Dynamic Programming] Sherlock and Cost (0) 2022.02.14 [자료구조] [python] [Dynamic Programming] Equal (0) 2022.02.12 [자료구조] [python] [Search] Cut the Tree (0) 2022.01.24 [정렬] 기수 정렬 알고리즘 (0) 2021.03.21 [자료구조] [python] [BFS/DFS] Shortest Reach in a Graph (0) 2021.02.25