[Algorithm] greedy

greedy

그리디 적용 가능한 예시

1. 필요한 동전 최소 개수 구하기

   큰 수부터 작거나 같은 값이 나오면, 기준 가격에서 나누기하여 동전 개수 구하는 방식

2. 카드 비교 최소 횟수 구하기

   작은 수끼리 비교하는 것이 가장 작으므로, 우선순위큐를 이용하여 작은 수끼리 비교한 합을 다시 큐에 넣어 계속 정렬된 작은 수를 비교하는 방식

3. 곱하기와 더하기를 사용하여 최대값 구하기

   양수, 음수, 0과 1을 따로 저장하여 계산하는 방식

4. 최대한 많은 회의실 이용하기

   끝나는 시간을 기준으로 정렬을 하여, 끝나는 시간 기준으로 시작시간을 가지는 회의를 선택하는 방식

5. 괄호를 이용하여 최솟값 구하기

    마이너스 뒤를 기준으로 전부 더하여 빼는 방식

---

1. 필요한 동전 최소 개수 구하기 https://www.acmicpc.net/problem/11047

11047번: 동전 0

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

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int N=input[0], K=input[1];
            int[] A = new int[N];

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

            int totalCoin = 0;
            for(int j=N-1; j>=0; j--){
                int price = A[j];
                if(price <= K){
                    totalCoin += K / price;
                    K = K % price;
                }
                if(K == 0) break;
            }
            System.out.println(totalCoin);
        } catch (Exception e) {
            System.out.println(e);
        }
    }
}

 

2. 카드 비교 최소 횟수 구하기 https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

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

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int N = Integer.parseInt(br.readLine());
            PriorityQueue<Integer> queue = new PriorityQueue<>();

            for(int i=0; i<N; i++){
                queue.add(Integer.parseInt(br.readLine()));
            }

            int sum = 0;
            while(queue.size() > 1){
                int num1 = queue.poll();
                int num2 = queue.poll();
                int sumNum = num1 + num2;
                sum += sumNum;
                queue.add(sumNum);
            }

            System.out.println(sum);
        } catch (Exception e) {
            System.out.println(e);
        }
    }
}

 

3. 곱하기와 더하기를 사용하여 최대값 구하기 https://www.acmicpc.net/problem/1744

1744번: 수 묶기

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

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

            ArrayList<Integer> plusArr = new ArrayList<>();
            ArrayList<Integer> minusArr = new ArrayList<>();
            int one = 0;
            boolean zero = false;
            for(int i=0; i<N; i++){
                int num = Integer.parseInt(br.readLine());
                switch (num){
                    case 0: zero = true;
                        break;
                    case 1: one += 1;
                        break;
                    default:
                        if(num > 0) plusArr.add(num);
                        else minusArr.add(num);
                }
            }

            int total = one;

            Collections.sort(plusArr);
            for(int i=plusArr.size()-1; i>=0; i-=2){
                if(i == 0) total += plusArr.get(i);
                else total += (plusArr.get(i)*plusArr.get(i-1));
            }

            Collections.sort(minusArr, Comparator.reverseOrder());
            for(int i=minusArr.size()-1; i>=0; i-=2){
                if(i==0) total += zero? 0: minusArr.get(i);
                else total += (minusArr.get(i)*minusArr.get(i-1));
            }

            System.out.println(total);
        } catch (Exception e) {
            System.out.println(e);
        }
    }
}

 

4. 최대한 많은 회의실 이용하기 https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

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

            ArrayList<Meeting> list = new ArrayList<>();
            for(int i=0; i<N; i++){
                int[] times = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
                list.add(new Meeting(times[0], times[1]));
            }

            Collections.sort(list, new Comparator<Meeting>() {
                @Override
                public int compare(Meeting o1, Meeting o2) {
                    if(o1.end == o2.end) return o1.start - o2.start;
                    else return o1.end - o2.end;
                }
            });

            int count = 0 ;
            int finish = -1;
            for(int i=0; i<N; i++){
                if(list.get(i).start >= finish){
                    finish = list.get(i).end;
                    count++;
                }
            }

            System.out.println(count);
        } catch (Exception e) {
            System.out.println(e);
        }
    }

    static class Meeting {
        int start;
        int end;

        Meeting(int start, int end){
            this.start = start;
            this.end = end;
        }
    }
}

 

5. 괄호를 이용하여 최솟값 구하기 https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

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

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] str = br.readLine().split("-");

            int total = 0;
            int[] input = Arrays.stream(str[0].split("\\+")).mapToInt(Integer::parseInt).toArray();
            for(int num: input){
                total += num;
            }

            for(int i=1; i<str.length; i++){
                int[] data = Arrays.stream(str[i].split("\\+")).mapToInt(Integer::parseInt).toArray();
                int sum = 0;
                for(int num: data){
                    sum += num;
                }
                total -= sum;
            }

            System.out.println(total);
        } catch (Exception e) {
            System.out.println(e);
        }
    }
}