동전교환 동적 계획법, 백준 동전1 문제 자바

동적 계획법 관련 알고리즘으로 백준의 동전이라는 문제이다. 동전의 수와 목표하는 동전의 최대가치가 주어지고, 동전의 수 만큼 각 동전의 가치가 주어질 때 여러 동전을 합해서 목표하는 가치를 채우는 경우의 수를 구하는 것이다. 알고리즘 자체는 크게 어려운 것 같지는 않은데, 동적 계획법은 알고리즘을 생각해 내는 것이 너무 어려운 것 같다. 아래가 주요 알고리즘이다. public static int cntCoin() { for (int i = 0; i < num; i++) { dp[value[i]]++; for (int j = value[i] + 1; j <= maxValue; j++) { dp[j] = dp[j] + dp[j - value[i]]; } } return dp[maxValue]; } 이 문제는 메모리의 제약이 커서 일차원 배열로 구현해야 한다. 어떤식으로 했냐면, 먼저 dp[동전 가치]를 하나 늘려준다. 그리고 그것의 배수, 예를들어 동전가치가 2이면 dp[2] = 1이 ...

원문링크 : 동전교환 동적 계획법, 백준 동전1 문제 자바