[코딩테스트] 백준 자바 11047번

오늘은 백준 11047 문제를 포스팅하겠다.

 

바로 들어가보자. 🔥

 

---

백준 문제 보기

11047번: 동전 0

 

문제 사진

 

그리디 알고리즘이

코딩 테스트 유형으로 많이 출제된다고 하여

풀어보았다.

 

생각보다 간단한 문제였다.

 

바로 코드를 살펴보자. 😊

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Q11047 {
    public static void main(String[] args) throws IOException {
        /*
        동전 종류 N (각 동전 매우 많음)
        K원을 만드는데 필요한 최소 동전 개수
         */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int shareN;
        int count = 0; // 동전 개수 

        // 동전 배열에 넣고 하나씩 나눠서 몫 저장

        int arr[] = new int[N];

        for(int i=0; i<=N-1; i++) {
            arr[i]= Integer.parseInt(br.readLine());

        }
        for(int i=N-1; i>=0; i--) {
            shareN = K/arr[i];
            count+=shareN;
            K-=shareN*arr[i];

        }
            System.out.println(count);
    }
}

 

첫번째 for문에서

동전 종류를 나타내는 변수(N)의 개수만큼

배열을 생성하고

 

두번째 for문에서

금액을 나타내는 변수(K)를 해당하는 동전의 값으로 나눠

몫을 카운팅하면

필요한 동전의 개수가 나온다.

 

이때, 역순으로 arr를 돌기 때문에

최소 동전 개수를 구할 수 있다.

 

어렵지 않은 문제이고

어렵지 않은 코드라 금방 이해할 수 있을 것이다.

(이해가 안되는 부분이 있다면

댓글 남겨주길 바란다.)

 

---

 

오늘은 코딩 테스트에서 자주 나오는

'그리디 알고리즘'의 첫 번재 문제를 풀어보았다.

 

더 열심히 공부하자. 😊