CodeAngie

문제 n가지 종류의 동전이 있다. 각 동전의 가치가 제시될 때, 그 가치의 합이 k원이 되도록 하는 경우의 수를 구하는 문제이다. 이때 순서가 달라도 구성이 같다면 같은 경우의 수이다. 풀이 이 문제는 dp를 사용해 풀 수 있다. 가치의 합이 k원(1 ≤ k ≤ 10,000)이 되도록 하는 경우의 수 문제를 나누어 가치의 합이 y(1 ≤ y ≤ k)가 되도록 하는 경우의 수를 구하는 부분 문제로 볼 수 있다. 동전 x1을 사용하여 y가 될 수 있는 경우가 성립하는지 확인하는 것이다. 다시 말해 y - x1을 만들 수 있는 조합이 있다면 해당 경우의 수만큼 x1을 가지고 y값을 만들 수 있다. 이를 통해 다음과 같은 식을 세울 수 있다. dp[y] = dp [y] + dp [y-x1] 알고리즘 dp 리스트..