💬 문제
문제 난이도: medium
문제 링크: https://www.hackerrank.com/challenges/coin-change/problem?isFullScreen=true
문제 설명
입력값으로 정수 n과 1차원 배열 c가 주어진다.
c에 담긴 원소들은 동전의 가치이다.
각 동전의 개수는 무한하다고 가정하고, 총합이 n인 동전의 조합의 개수를 구하라.
예를 들어 n = 3, c = [1, 2, 3, 8]이라고 하자.
{1, 1, 1}, {1, 2}, {3}. 이렇게 총 3개의 조합이 있다.
❗️접근 방법
DP(dynamic programming)
DP 테이블
dp[i][j]
: i번째 동전까지 사용했을 때 동전의 합이 j인 조합의 개수
코드
def getWays(n, c):
dp = [[0] * (n+1) for _ in range(len(c))]
# 0번째 동전만 사용했을 때 총합이 1부터 n까지 만들어질 수 있는지
# 만들 수 있다면 1로 초기화
for i in range(1, n+1):
if (i % c[0] == 0):
dp[0][i] = 1
for i in range(1, len(c)):
# i번째 동전으로 만들 수 있는 가장 작은 수(c[i])에 +1
if c[i] <= n:
dp[i][c[i]] += 1
# i번째 동전까지 사용했을 때 총합이 1부터 n까지 만들어질 수 있는지
for j in range(1, n+1):
# 총합(j)보다 동전의 가치(c[i])가 더 크면
# i번째 동전을 포함한 조합을 만들 수 없음
# i-1번째 동전까지 사용했을 때의 개수를 그대로 넘겨줌
if j < c[i]:
dp[i][j] = dp[i-1][j]
# dp[i-1][j] : i번째 동전을 포함하지 않으면서 총합 j를 만드는 경우
# i-1번째 동전까지 사용하면서 총합 j를 만드는 경우
# p[i][j-c[i]] : i번째 동전을 포함하면서 총합 j를 만드는 경우
# i번째 동전을 사용하면서 총합이 j-c[i]인 경우
else:
dp[i][j] = dp[i-1][j] + dp[i][j-c[i]]
return dp[len(c)-1][n]1. 0번째 동전까지 사용한 경우를 따로 빼서 초기화한 이유
dp 특성상 i번째 동전까지 사용할 때 i-1번째 동전까지 사용하는 경우에 i번째 동전을 포함할 것인지 아닌지를 더하게 된다.
그런데 i가 0이라면 i-1은 -1로, 원하는 인덱스 범위에서 벗어난다.
따라서 0번째 동전까지 사용한 경우, 즉 0번째 동전만 사용한 경우만 따로 초기화시켜준다.
※ python에서 배열[-1]은 indexError를 일으키지 않고, 배열의 마지막 원소를 가리킨다.
error가 발생하지 않기 때문에 인덱스의 범위에 대해서 기준을 따로 세워야 한다
2. dp[i]c[i]] += 1 하는 이유
i번째 동전을 포함할 수 있는 가장 작은 j는 c[i]일 때이고
i번째 동전만 사용한 경우이고 하나의 조합만 가지므로 +1 를 해준다.
이전 dp 테이블을 참고할 필요도 없고 참고할 수도 없다.
i번째 동전을 포함한 경우는 i~n까지 행에 적혀질 것이고
i번째 동전을 포함한 경우 만들 수 있는 가장 작은 수가 c[i]이기 때문이다.
3. dp[i][j] = dp[i-1][j] + dp[i]j-c[i]]에서 dp[i-1][j]가 아니라 dp[i][j]인 이유
dp[i][j]는 i번째 동전까지 사용해 총합이 j이 조합의 개수이다.
이때 i번째 동전을 포함해 조합을 만드는 개수와 포함하지 않고 조합을 만드는 개수로 나눌 수 있다.
i번째 동전을 포함하지 않는 경우는 dp[i-1][j], 즉 i-1번째 동전까지 사용해서 총합 j를 만드는 조합의 개수이다.
반면 i번째 동전을 포함하는 경우는 dp[i]j-c[i]]인데, 이 부분이 처음엔 잘 이해되지 않았다.
예시를 들어 설명해보자면
n = 9, c = {2, 4}
1번째 동전까지 사용해서 총합이 8인 조합은
{2,2,2,2}, {2,2,4}, {4,4}로 총 3개이다.
1️⃣ 1번째 동전을 포함하지 않는 경우: {2,2,2,2}
2️⃣ 1번째 동전을 포함한 경우 경위 {2,2,4}, {4,4}
2️⃣에서 1번째 동전(4원)를 포함하는 경우는 8-4= 4원을 만들 수 있는 조합의 개수이고
4원을 만들 수 있는 조합은 0번째 동전까지 사용한 경우가 아니라 1번째 동전까지 사용한 경우이다.
그렇지 않다면 4를 만드는 조합으로 {2,2}만 사용되고 {4}는 사용되지 않아
{2,2,2,2}, {2,2,4}로 2개가 되므로 모든 경우의 수를 따지지 못한다.
따라서 dp[i-1]j-c[i]] 가 아니라 dp[i]j-c[i]]이다.
