[백준] 11047번 동전 0

그리디 알고리즘 문제 !

동전개수의 최솟값을 구해야 하므로, 큰 단위부터 비교하기 위해

입력받은 배열을 내림차순 정렬 하였다.

 

 

1차 제출

package 백준.greedy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;

public class baekjoon_11047 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int K = Integer.parseInt(str[1]);

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

        Arrays.sort(arr, Collections.reverseOrder());

        int count = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] < K) {
                count += K / arr[i];
                K %= arr[i];
            }
        }
        System.out.println(count);
    }
}

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;

public class baekjoon_11047 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        int N = Integer.parseInt(str[0]);
        int K = Integer.parseInt(str[1]);

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

        Arrays.sort(arr, Collections.reverseOrder());

        int count = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] <= K) {
                count += K / arr[i];
                K %= arr[i];
            }
            if (K==0) break;
        }
        System.out.println(count);
    }
}

 

arr[i] 값이 K 값과 같은 경우에도 진행될 수 있도록 함

K==0인 경우 반복문 탈출