[알고리즘][다이나믹(동적 계획법) 기초] 동전1 (백준)

동적 계획법 알고리즘 기초문제 - 동전1 (백준)

기존에 풀어오던 동적 계획법과 조금 다른 방식으로 접근을 해야해서

시간이 조금 오래걸렸다. 알고리즘을 오랜만에 풀어서기도 하겠지만

여전히 점화식을 세우는 것이 상당히 어렵게만 느껴진다.

이번 문제는 동전을 주고 해당하는 값을 이 동전으로 채울려면 몇 개의 경우의 수가 있느냐이다.

문제는 1,2,5원이 주어지고 10원을 채워야할 때 과연 경우의 수가 얼마인가.. 였다..

문제를 딱보자마자 dp배열에 다 때려박은 다음에 10원까지 쭉올라가다보면

답이 알아서 나오겠구나.. 생각했다..

기존에 동적 계획법을 풀때에는 답을 찾은 dp배열은 다시 건들지 않았다.

하지만 이번 문제는 답을 한번에 찾고 넘어가는 것이 아니라

다시 돌아와서 갱신을 해가면서 풀어야 한다는 것이다.

물론 기존에 찾은 답을 바탕으로 현재의 답을 찾는다는 동적 계획법의 기본은 충실하면서

동적 계획법 알고리즘 기초문제 - 동전1 (백준)

처음 들었던 생각은 1,2,3,4,5.... 차례로 쭉올라가면서 해당되는 값의 경우의 수를 찾아내고

그 수를 바탕으로 어떠한 점화식을 세운다면 답이 수월하게 나올줄 알았다.

하지만 값이 점점 커질수록 사용되는 동전의 수가 늘어나고 어떠한 규칙에도 예외가 생겨버렸다..

이 규칙을 찾으려 상당히 오랜시간을 고민했다. <-- 틀에 박힌 사고의 문제점

이 문제의 해답은 바로 dp배열을 점차 갱신해가며 답을 찾아 나간다는 것!

1,2,5원의 동전이 주어졌을 경우를 예로들어 설명을 하면

1. 1원 밖에 주어지지 않았을 때 1~k 값을 채울 수 있는 경우의 수를 구한다.

2. 2원 밖에 주어지지 않았을 때 2~k 값을 채울 수 있는 경우의 수를 구한다.

3. 5원 밖에 주어지지 않았을 때 5~k 값을 채울 수 있는 경우의 수를 구한다.

5원 밖에 주어지지 않았을 때 5원 이하의 값들은 5원의 영향을 받지 않기 때문에 제외.

하.. 동적 계획법은 정말 수학적 머리가 타고나야 하는 것 같다.

DFS, BFS의 경우에는 원리를 이해만한다면 어느정도 풀기가 수월하지만

동적 계획법은 공부를 하면 할수록 더욱 어려워 지는 것 같다..