스파르타 알고리즘 트랙 문제 6일차 - 3 #11047 동전 0

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

해결 과정

DFS를 구현한 후 그리디 서치를 해야겠다는 생각을 했으나, 문제의 동전 조건이 1부터 시작하여 배수로 증가하는 배열이기에 금액이 큰 동전부터 고려한다면 큰 문제없이 해결할 수 있는 문제가 되었다.

import java.io.*; import java.util.*; public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int N = sc.nextInt();         int money = sc.nextInt();         int cnt = 0;         Stack<Integer> stack = new Stack<>();         for(int i = 0; i<N;i++){             stack.add(sc.nextInt());         }         for(int j = 0; j< stack.size();j++){             cnt = cnt + (money/stack.peek());             money = money%stack.pop();         }         System.out.println(cnt);     } }

N이 주어지기에 크기가 N인 배열을 생성해 이전 문제에서 사용했던 최대, 최소를 구하는 방법을 활용해도 괜찮으나, 동전의 입력값이 작은 수 부터 큰 수 순으로 주어지기에 배열 대신 Stack을 사용해 문제를 풀어보았다.

 

동전의 액수를 전부 Stack에 저장한 후, 보유한 금액을 Stack에서 꺼내온 값으로 나눈 몫이 해당 동전의 갯수가 된다. 이를 stack이 모두 소진될 때까지 반복한다. Stack의 가장 처음에는 1이 들어가므로 최종적으로 나머지가 남을 경우는 발생하지 않는다.

 

그러나 위의 코드는 정답이 아니라는 답변을 받았다. 어떤 것이 잘못되었나 다시 한 번 확인해 본 결과, 두 번째 for 문에서 stack.pop으로 인해 감소한 size가 다시 for문에서 감지하여 실질적으로는 N번 반복해야 하는 반복문이 N/2번만 반복하게 된 것이다.

 

모든 Stack을 다 채운 후의 Stack의 크기는 N과 동일하므로 stack.size()를 N으로 대체하여 실행해 보았다.

import java.io.*; import java.util.*; public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int N = sc.nextInt();         int money = sc.nextInt();         int cnt = 0;         Stack<Integer> stack = new Stack<>();         for(int i = 0; i<N;i++){             stack.add(sc.nextInt());         }         for(int j = 0; j<N;j++){             cnt = cnt + (money/stack.peek());             money = money%stack.pop();         }         System.out.println(cnt);     } }

위의 코드는 큰 문제 없이 정상적으로 돌아가였고, 정답임을 확인할 수 있었다.