[Algorithm] 백준 단계별로 풀어보기 - 단계 13. 그리디 알고리즘

그리디(탐욕) 알고리즘 응용하기

11047. 동전 0

동전 개수의 최소값을 찾아야하므로 최선의 선택은 가장 큰 금액에서부터 빼는 것

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

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

        int cnt = 0;
        for(int i=N-1; i>=0; i--) {
            while(coin[i] <= K) {
                K = K - coin[i];
                cnt++;
            }
            if(K <= 0) break;
        }
        System.out.print(cnt);
    }
}

1931. 회의실 배정

2차원 배열을 정렬하는 방법에 대해 알아야 한다. 기존 정렬과 다르게 정렬하고 싶을 때는 Comparator를 이용한다.

* compare() 메서드
첫 번째 파라미터로 넘어온 객체 < 두 번째 파라미터로 넘어온 객체: 음수 리턴
첫 번째 파라미터로 넘어온 객체 == 두 번째 파라미터로 넘어온 객체: 0 리턴
첫 번째 파라미터로 넘어온 객체 > 두 번째 파라미터로 넘어온 객체: 양수 리턴

 

회의를 종료 시간 기준 오름차순 정렬, 종료 시간이 같을 경우에는 시작 시간 기준으로 정렬되었다면 이에 따라 회의를 배정하면 된다.

종료 시간이 같을 경우 시작 시간으로 정렬해주어야한다!

2 2 / 1 2 와 같이 배열이 존재하는 경우 이를 시작시간 기준으로 정렬해주지 않으면, 그리디 알고리즘에서는 2 2를 선택하기 때문이다.

 

1 4 (end = -1)

3 5

0 6

5 7 (end = 4)

3 8

5 9

6 10

8 11 (end = 7)

8 12

2 13

12 14 (end = 11)

 

종료 시간을 가지고 있는 변수를 하나 선언하고 0보다 작은 수로 초기화해준다.

index 0 일 때 시작 시간이 종료 시간보다 크므로 회의를 배정하고(카운트 증가), index 0의 끝나는 시간인 4를 end에 넣는다.

시작 시간이 4보다 큰 것을 찾는다. index 1, 2는 이에 해당되지 않는다.

index가 3일때 시작 시간이 5이므로 회의를 배정하고, 끝나는 시간인 7을 end에 넣는다.

 

이러한 식으로 계속해서 반복하며 문제를 풀여주면 됨.

모든 경우를 고려해서 문제를 해결해 나아가는 dp와는 다르게 해당 상황에서의 최선을 선택해서 푸는 문제이다.

package algorithm.Baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class BOJ_1931 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[][] time = new int[N][2];
        for(int i=0; i<N; i++) {
            String[] input = br.readLine().split(" ");
            time[i][0] = Integer.parseInt(input[0]);
            time[i][1] = Integer.parseInt(input[1]);
        }

        //끝나는 시간 순 정렬
        Arrays.sort(time, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                //0: 시작 시간, 1: 종료 시간
                //끝시간이 같을 경우 시작 시간 정렬
                if(o1[1] == o2[1]) {
                    return Integer.compare(o1[0], o2[0]);
                }
                //종료 시간 정렬
                return Integer.compare(o1[1], o2[1]);
            }
        });

        //회의 배정하기
        int cnt = 0, end = -1;
        for(int i=0; i<N; i++) {
            if(time[i][0] >= end) {
                end = time[i][1];
                cnt++;
            }
        }
        System.out.print(cnt);
    }
}

11399. ATM

기다리는 시간의 합을 최소화하는 문제

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

public class BOJ_11399 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] result = new int[N];
        for(int i=0; i<N; i++) {
            result[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(result);
        int sum = 0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<=i; j++) {
                sum += result[j];
            }
        }

        System.out.print(sum);
    }
}