백준 11047 동전 0 [JAVA]

문제 해석

• 문제는 크게 어렵지 않아서 간단하게 설명하고 코드로 넘어가서 주석으로 남겨둘 예정이다. (주석으로만 설명해도 충분히 이해 가능:))
• 첫째 줄에 N(동전의 총 종류 개수)와 만들고자하는 금액(가치의 합, K)를 입력받는다.
• 두번째 줄부터는 N개의 동전 가치 값을 입력 받는다. (한줄 씩)
• 모두 입력받았다면, 금액 K를 만들기 위해 들어가는 동전의 최소 개수를 구하면 된다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); //동전의 총 종류
        int K = Integer.parseInt(st.nextToken()); //만들어야하는 금액
        
        int[] coinArr = new int[N]; //동전의 종류(가치)별로 넣는 배열
        
        for(int i = 0;  i < N; i++){ //동전의 총 종류 수만큼
            coinArr[i] = Integer.parseInt(br.readLine()); //동전 가치 넣기 
        }

        br.close();

        int cnt = 0; //코인 넣는 횟수
        //동전이 큰 값부터 비교해야 더 적게 비교할 수 있으므로 거꾸로 반복문을 진행한다.
        for(int i = N-1; i >= 0; i--){
            if(coinArr[i] <= K){
                //현재 반복문이 돌고 있는 동전의 값을 넣을 수 있는 만큼 넣는다.
                // 큰 값 -> 작은 값 이기 때문에 큰 값이 많이 들어가야 K(금액)을 만들기 위해 최소 동전 개수를 구할 수 있다.
                cnt += (K / coinArr[i]);
                K = (K % coinArr[i]); //K(금액)을 갱신(그래야 초기 K값을 -하여 만들 수 있기 때문)
            }
        }

        bw.write(cnt+"\n");
        bw.flush();
        bw.close();


    }
}

결과

느낀 점

그리드 알고리즘으로 넘어오면서 꽤 오랫동안 했던 동적 프로그래밍 -> 누적합까지 계속해서 쉽지않던 문제들만 풀어오다가 잠시 쉬어가는 느낌의 문제를 만난 느낌..이랄까?? 물론 그리드 알고리즘을 적용하는 첫 문제여서 그런 거겠지만 풀다가 벽을 만나지 않도록 다음 포스트는 그리드 알고리즘에 대해 정리한 내용이 올라갈 것 같다!