그리디 알고리즘(11047, 1931)

[동전0 _ 11047]

 

 

* 조건

1. 각각의 금액 가치가 존재하는 동전의 종류 N개가 주어진다
2. 동전의 가치는 오름차순 순으로 정렬되어있다
3. 원하는 금액 K를 만들 수 있는 동전의 최소 개수를 구한다

* 알고리즘

- 최적의 상태를 발견하면 없을 때까지 계속 해당 상태를 진행: 그리디 알고리즘

 

* 로직(Logic)

- 동전의 가치가 제일 큰 경우부터 K 금액을 나누어 몫이 존재하면 동전의 개수로 추가시켜준다

- 나머지 값을 K로 덮어준다 (해당 금액만 구하면 되니까)

- 몫이 존재하지 않게되면 그 다음 동전을 선택하고 위 과정을 반복한다

 

import java.util.Scanner;

public class Problem_11047 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        int[] coins = new int[n];
        for(int i=0; i<n; ++i){
            coins[i] = scanner.nextInt();
        }

        int tmp = k;
        int a=n-1;
        int cnt = 0;
        while (a >= 0){
            int coin = coins[a];
            if((tmp / coin) > 0){
                cnt += tmp / coin;
                tmp = tmp % coin;
            }
            a--;
        }

        System.out.println(cnt);
    }
}

 

[회의실 배정 _ 1931]

 

 

* 조건

1. 회의의 수: N (1 <= N <= 100000) -> 브루트포스를 적용하면 시간초과
2. 회의의 시작 시간과 끝나는 시간이 주어진다
3. 회의가 끝나는 동시에 다른 회의를 시작할 수 있다
4. 최대로 사용할 수 있는 회의 수를 구한다

* 알고리즘

- 그리디 알고리즘

 

* 로직(Logic)

- 끝나는 시간이 짧을수록 더 많은 회의를 할 수 있기 때문에 -> 끝나는 시간을 기준으로 오름차순 정렬

- for문을 돌면서 (끝나는 시간 <= 시작시간)인 인덱스를 찾고 끝나는 시간을 해당 인덱스의 끝나는 시간으로 덮어주고 카운팅한다

 

import java.util.Arrays;
import java.util.Scanner;

class Time_1931 implements Comparable<Time_1931>{
    public int startTime, finishTime;

    public Time_1931(int startTime, int finishTime) {
        this.startTime = startTime;
        this.finishTime = finishTime;
    }

    @Override
    public int compareTo(Time_1931 o) {
        if(this.finishTime > o.finishTime) return 1;

        else if(this.finishTime == o.finishTime){
            if(this.startTime > o.startTime) return 1;
        }
        return -1;
    }
}

public class Problem_1931 {

    static int n;
    static Time_1931[] timeTable;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        timeTable = new Time_1931[n];

        for(int i=0; i<n; ++i){
            timeTable[i] = new Time_1931(scanner.nextInt(), scanner.nextInt());
        }
        Arrays.sort(timeTable);

        int finishTime = -1;
        int count = 0;
        for(int i=0; i<n; ++i){
            if(timeTable[i].startTime >= finishTime){
                finishTime = timeTable[i].finishTime;
                count++;
            }
        }

        System.out.println(count);
    }
}