섹션 10. dynamic programming(동적계획법) 5. 동전교환(냅색 알고리즘)

문제

• 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?
• 각 단위의 동전은 무한정 쓸 수 있다.

입력

• 첫 번째 줄에는 동전의 종류개수 N(1<=N<=50)이 주어진다.
• 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
• 각 동전의 종류는 100원을 넘지 않는다.

출력

• 첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

입출력 예제

---

풀이방식

이번 문제는 동적 계획법(dynamic programming)에 대한 문제이다.

동적 계획법 이란 시간 복잡도가 큰 문제를 직관적으로 작게 나눈다. 이렇게 나누어진 작은 문제들을 메모이제이션을 사용해서 최종적으로 본래 문제의 해결방안을 찾는 것을 말한다.

---

설계과정

1. dy 배열을 최대값으로 초기화한다.

2. dy[ ] 배열의 0번째에 0을 넣는다.

3. arr 배열에 입력받은 동전의 종류들을 coin 배열로 넘긴 후, for문을 통해 dy 배열에 값을 변경한다.

4. coin 배열을 통해 입력받은 동전에 따라 dy[ ] 배열의 값을 변경한다.

5. dy[M] 을 출력한다.

---

풀이과정

1.  각 변수들을 선언한다.

• coin[ ] : 입력받은 동전의 종류
• dy[ i ] : i 라는 금액을 만드는데 드는 최소 동전의 개수

2. dy 배열을 최대값으로 초기화한다.

• Arrays.fill(배열 변수, 배열 데이터) : 배열의 모든 값을 같은 값으로 초기화하는 메소드이다.

3. dy[ ] 배열 0번째에 0을 저장한다.

• dy[0]은 0원을 가지고 구할 수 있는 개수를 의미하는데, 0은 없으므로 0으로 저장한다.

4. 0부터 N 전까지 도는 for문을 작성하고, 그 안에 coin[i] 부터 M까지 도는 for문을 통해 dy[ j ] 배열에 값을 넣는다.

• j 는 입력받은 동전들의 종류를 가진다. 문제 예시로 보면 1, 2, 5 라는 값을 가지게 된다.

5. dy[ j ] 에는 dy[ j ] 와 dy[j - coin[i]] + 1 를 비교해서 더 작은 값을 넣는다.

• j가 1이라면 dy[1]부터 시작하고 j가 5라면 dy[5]부터 시작한다.
• j라는 동전을 사용해서 dy 배열의 인덱스마다 해당 금액을 만드는데 드는 최소 동전의 개수를 구한다.
• 즉, j가 1이라면 1원으로 0~15까지 금액을 만들 수 있는 최소 개수를 dy 배열에 넣는것이다.
• 그 후에 j가 2가 된다면, 2~15까지 금액을 만들 수 있는 최소 개수를 구하여 넣는다.
• 이 때 dy[2]를 예시로 보자면, 1일 때에 해당 인덱스에는 '2' 라는 값이 들어갔다. 그러나 j=2 인 상황에서 보면 2원은 '2원 짜리 동전 1개' 로 충분하기에 dy[2]는 1로 값이 변하게 된다.

6. dy[M] 을 출력한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.