[BOJ] C++ 9084: 동전 - DP의 핵심은 중복 제거!

https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 예제 3 2 1 2 1000 3 1 5 10 100 2 5 7 22 ans : 501 121 1 주어진 n개의 동전으로 숫자 m을 만드는 방법의 수를 구하는 문제이다. 가장 먼저 떠오르는 방법은 역시 완전탐색이다. 최대 20개의 동전을 종류별로 다 더해주면서 계산하면 답이 나올 것 같긴 한데 굉장히 오래 걸리고 중복이 많이 발생할 것 같았다. 따라서 완전탐색은 안된다 생각하고 1,..

2023.12.20