✓

태그:

22. 동적 계획법 2

사용할 수 있는 동전의 가짓수를 DP로 하되 한 번 확인한 동전은 다시 쓰면 안돼요…!!

풀이 비스무리한거 보기

주어진 가치를 가진 n종류의 동전이 무한히 있을 때, k의 가치를 만들 수 있는 동전 조합의 수를 구하는 문제입니다. 이 문제는 사용할 수 있는 동전의 가짓수를 추가하면서 구해가는 DP 문제입니다.

먼저 DP를 사용하는 것은 0의 가치를 만드는 경우가 1가지 있다고 하고, 각 동전마다 지금까지 만들 수 있는 가치에 해당 동전의 가치를 더하여 새로운 가치를 만드는 경우의 수를 정해주는 것입니다. 그 코드는 아래와 같습니다.

cases[v + val[c]] += cases[v];

이를 반복하면 결과값을 얻을 수 있습니다. 하지만 여기서 유념해야 할 점은 메모리의 제한이 상당히 작다는 점입니다. 따라서 DP를 할 때, DP 배열을 가치/동전의 종류로 하여 2차원 배열로 선언하면 메모리가 부족합니다. 따라서 사용한 동전의 종류는 DP에 넣지 않고, 값을 업데이트하면서 겹치지 않도록 작은 가치부터 순서대로 경우의 수를 업데이트하면 됩니다.

소스 코드

언어	코드	시간	비고
C++	코드(Github) / 코드(백준)	2021-01-23 23:46:54

---