아이디어는 간단하다. 목표 금액 k의 범위가 작기 때문에, k까지 담을 수 있는 배열을 준비한 뒤, 그 배열을 각각의 동전을 이용해 순회를 한다. 순회를 할 때 배열의 인덱스를 금액, 값을 그 금액을 만들 수 있는 동전의 최소 개수를 넣어주며 모든 동전을 이용해 순회한다.
모든 동전이 끝난 뒤, k 번 인덱스의 값이 필요한 동전의 최소 개수다.
아마 DP에 익숙하다면 위의 설명만 가지고 이해를 했을 것이다. DP에 익숙하지 않다면 이 문제를 통해 DP에 조금 더 익숙해져 보자.
문제를 풀기 위한 규칙이다.
(규칙 A) 이번에 순회할 동전의 가치와 같은 인덱스의 값을 1로 만들어준다.
(규칙 B) 순회는 맨 앞칸부터 시행하며, (현재 조회 중인 인덱스 + 현재 동전의 가치)가 k를 넘으면 종료하여 다음 동전으로 넘어간다.
(규칙 C) 순회 도중 (현재 조회 중인 인덱스 + 현재 동전의 가치) 위치의 값이, (현재 조회 중인 인덱스의 값 + 1) 보다 크다면, 값을 경신한다. (또는, (현재 조회 중인 인덱스 + 현재 동전의 가치) 위치를 한 번도 간 적이 없다면 갱신한다.)
(규칙 D) 모든 순회가 끝난 뒤, k인덱스의 값이 정답이다.
규칙을 말로 표현하기 조금 까다롭다, 예시 이미지 또한 글씨가 많아서 어렵게 느껴질 수 있다.
아래의 예시를 보며 하나하나 이해해보자.
문제의 예제 입력을 나타내 본 그림이다.
여기서 점프 단위는 동전의 가치와 같다, (규칙 C)를 쉽게 표현하기 위해 추가로 표기했다.
(규칙 A) 적용 점프 단위 (= 이번 동전의 가치)에 해당하는 인덱스 값을 1로 만들고 시작한다. 이유는 5원 동전을 순회할 때 이해하기 쉬우니 일단은 규칙대로 진행해보자.
(현재 조회 중인 인덱스 + 현재 동전의 가치) 위치 = (1 + 1) = 2번 칸을 한 번도 간 적이 없다. (= 초기값이다) (규칙 C)를 적용할 수 있다.
(규칙 C)를 적용하며 순회 중이다. 개념적으로는 (1원은 1원짜리 동전 1개, 2원은 1원짜리 2개, 3원은 3원짜리 3개......)인 상황이다.
(규칙 B)에 의해 다음 동전으로 넘어가자.
여기서 (규칙 A)의 의미를 더 쉽게 알 수 있다.
1원짜리 5개보다, 5원짜리 1개가 더 적은 개수이며, N원짜리 동전을 쓰면 N원의 위치는 항상 1개로 갈 수 있다. 즉 점프 단위 (=동전의 가치) 인덱스의 값은 항상 최솟값인 1 이 된다.
이후 (규칙 C)를 적용해 탐색을 지속한다.
10원을 만드는 방법은 여러 개가 있지만 (1원 10개 vs 1원 5개 + 5원 1개 vs 5원 2개) (규칙 C) 만으로 최솟값을 계속 갱신해 나갈 수 있다.
이대로 순회를 쭉 해 나가면 마지막 15원 지점에서도 DP의 강점이 나타난다.
15원을 만들기 위해 필요한 동전의 최소 개수는 3개 (= 5원 3개)이다.
DP는 단독으로 사용될 수 도 있지만 다른 알고리즘과 조합되기 좋은 기본기 중 하나이다. (예를 들어 BFS와 DP를 조합하여 Dijkstra를 만들어 낸다.) 응용을 위해 "DP의 느낌"을 느낀 뒤 다양한 문제 풀이를 해보기를 추천한다.
