섹션 8. DFS, BFS 활용 5. 동전교환

문제

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

입력

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

출력

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

입출력 예제

---

풀이방식

이번 문제는 재귀함수에 대한 문제이다.

 

---

재귀함수에 대한 자세한 설명은 아래 글을 참조하길 바랍니다.

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 1. 재귀함수(스택프레임)

섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 1. 재귀함수(스택프레임)

---

설계과정

이전에 풀었던 부분집합 문제와 거의 비슷하다.

1. 시간제한에 걸리지 않기 위해 값을 입력 받은 후, 배열을 정렬한다.

2. 금액의 총합이 M보다 크면 리턴한다.

3. 금액의 총합이 M과 같다면 result와 L 중에서 작은 값을 리턴한다.

4. 부분집합에 사용하지 않을 때에는 DFS(L+1, sum, time, ps, pt) 을 매개변수로 넣어준다.

---

풀이과정

1. 각 변수들을 선언 및 초기화한다.

• result : 결과를 저장할 변수로, Integer.MAX_VALUE 를 통해 최대값으로 초기화한다.
• sum : 금액의 총합이다.
• arr[ ] : 동전의 종류들이 들어가있는 배열이다.
• L : 사용된 동전의 개수

2. 배열을 내림차순으로 정렬한다.

• Arrays.sort() : 배열을 오름차순으로 정렬한다.
• Collections.reverseOrder() : 해당 옵션을 추가하여 배열을 내림차순으로 정렬한다.

3. DFS 메소드를 작성한다.

 

4. 금액의 총합이 M보다 크면 리턴하고, 사용된 동전의 개수가 결과값보다 크거나 같다면 리턴한다.

 

5. 금액의 총합이 M과 같다면 result와 L 중에서 작은 값을 리턴한다.

 

5. 그게 아니라면 탐색을 계속한다. 다음 탐색을 위해 L+1, sum+arr[i], arr 을 매개변수로 넣어준다.

• 동전의 개수에 1을 증가시킨다.
• sum에 금액의 총합을 넣어야하기 때문에 해당 배열의 값을 더하여 누적한다.

---

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