[백준 #11047] 동전 0

백준 #11047 동전 0

백준 #11047

---

문제 설명👩‍🏫

가지고 있는 동전을 적절히 사용해 필요한 돈을 최소한의 동전 개수로 만들기

입출력 예

입력
10 4200
1
5
10
50
100
500
1000
5000
10000
50000

출력
6

---

내 코드💻

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringTokenizer st = new StringTokenizer(str," ");

        int n = Integer.parseInt(st.nextToken());
        int sum = Integer.parseInt(st.nextToken());
        int change;
        int answer = 0;
        int index = n-1;
        int [] value = new int[n];

        for(int i=0;i<n;i++){
            str = br.readLine();
            value[i] = Integer.parseInt(str);
        }

        for(int i=n-1;i>=0;i--){
            if(value[i] <= sum){
                index = i;
                break;
            }
        }

        for(int i=index;i>=0;i--){
            int num = sum / value[i];
            change = sum - (value[i] * num);
            answer += num;
            sum = change;

            if(sum == 0){
                System.out.println(answer);
                break;
            }
        }

    }
}

---

설명💡

문제를 봤을 때는 필요한 값만큼 가치가 큰 순서부터 차례로 구하고, 남은 건 그 다음 작은 값으로 나누면 되지않나 생각했다. 그러다 만약 동전을 제시할 때 100원, 400원, 500원 이런 식으로 나올 수도 있는건가 하는 생각도 들었지만 입력 조건에 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 이 말을 보고 그럴 가능성은 없구나 깨닫고, 처음 생각한 방식대로 하면 되겠구나 느꼈다.

---

sum에는 총 가치의 합이고, change는 중간에 쓰일 나머지값을 저장해둘 변수이다. index는 가치보다 작은 값 중 가장 큰 값을 저장해두기 위한 변수다.
세 번째 for문에서 num은 가치를 value[i]로 나눴을 때 나머지값을 잠시 저장하기 위한 변수이다.

---

실수한 부분😟

for(int i=n-1;i>=0;i--){
            if(value[i] < sum){
                index = i;
                break;
            }
        }

처음에 시도할 때 index값을 정할 때, sum보다 작은 값으로 설정해서 만약 입력이 2 500 / 1 / 500 으로 들어왔다면 index 값이 0으로 설정되어 500이 출력되게된다..
그래서 if(value[i] <= sum) 으로 변경했다.

---

느낀 점 및 궁금한 점🍀

테스트 코드를 작성하는 연습을 더 하면 좋을 것 같다.. 왜 매번 똑같은 느낌만 떠올라서.. 다른 테스트 코드가 떠오르면 실수를 더 빨리 발견 할 수 있을 것 같다...😭