백준 14916, 1092번(스터디)

알고리즘 풀기(스터디)

목록 보기

2/2

문제 14016번

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

요약

거스름돈을 2원, 5원 동전으로만 만들어야 하는 문제.
목표: 동전 개수를 최소로 사용해야한다.
정확히 나누어 떨어지지 않으면 -1 출력한다.

접근법

5원과 2원밖에 없으므로 2원보다 큰 5원을 가장 많이 써야 최소한의 동전을 사용했다는 결론.
따라서 전체 값의 5를 나눴을 때 나머지가 0이나오면 베스트이고 나머지값을 2로 나눴을 시 나누어 떨어지면 그 동전의 개수가 가장 최소한의 개수가 될 것임.
다만 나누어 떨어지지 않을 경우 5원을 빼가면서 다시 계산을 해주어야하고 다 빼서도 안되면 -1을 반환시키면 된다.
n(전체값) = 5a(5원) + b(나머지)
b = n % 5

b = 0 → OK

b = 1 → 2원으로 만들 수 없음 → 5원 1개 빼서 조정 필요

b = 2 → 2원 1개로 가능

b = 3 → 2원으로 만들 수 없음 → 5원 1개 빼서 조정 필요

b = 4 → 2원 2개로 가능

b가 1, 3일 경우에만 5원을 하나씩 빼서 재계산을 해야한다.
다만!! n자체가 1, 3이 들어올 경우에는 예외처리를 해주어야한다.

코드

package Sutdy;

import java.util.Scanner;

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

        // n값 자체가 1, 3일경우엔 -1을 반환하도록 예외처리
        if (n == 1 || n == 3) {
            System.out.println(-1);
            return;
        }

        // 5원의 개수
        int fiveNum = n / 5;

        // 나머지 1 또는 3 → 5원 하나를 뺌
        if (n % 5 == 1 || n % 5 == 3) {
            fiveNum -= 1;
        }

        // 나머지 값
        int remainder = n - (fiveNum * 5);

        // 2원의 개수
        int twoNum = remainder / 2;

        //합친 것 (5로 딱 떨어질 경우 2원의 개수는 0으로 채워지기 때문에 이상 없음)
        System.out.println(fiveNum + twoNum);
    }
}

문제 1092번

지민이는 항구에서 일한다. 그리고 화물을 배에 실어야 한다. 모든 화물은 박스에 안에 넣어져 있다. 항구에는 크레인이 N대 있고, 1분에 박스를 하나씩 배에 실을 수 있다. 모든 크레인은 동시에 움직인다.

각 크레인은 무게 제한이 있다. 이 무게 제한보다 무거운 박스는 크레인으로 움직일 수 없다. 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보다 작거나 같은 자연수이다. 넷째 줄에는 각 박스의 무게가 주어진다. 이 값도 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 출력한다. 만약 모든 박스를 배로 옮길 수 없으면 -1을 출력한다.

요약

여러 개의 크레인 → 각각 들 수 있는 최대 무게가 다름
박스도 여러 개 → 각 박스마다 무게가 있음
1분에 각 크레인이 박스 1개씩만 이동 가능
모든 박스를 옮기는 데 걸리는 최소 시간을 구하는 문제

접근법

가장 무거운 크레인부터 작업시키기
- 이유 : 무거운 크레인만 들 수 있는 박스가 있기 때문
크레인 리스트와 박스 리스트를 내림차순 정렬
- 둘 다 큰 것부터 매칭하면 관리가 훨씬 쉬워짐
반복문 시간 단위로 진행
- 한 번의 루프가 1분을 의미
- 각 크레인이 할 수 있는 박스를 “순서대로” 찾아서 옮김
- 박스를 옮기면 그 박스는 리스트에서 제거
- 박스를 못 옮긴 크레인은 그냥 다음 분으로 넘어감

코드

package Sutdy;

import java.util.*;

public class Beak1092_Greedy {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        List<Integer> cranes = new ArrayList<>();
        for (int i = 0; i < N; i++) cranes.add(sc.nextInt());

        int M = sc.nextInt();
        List<Integer> boxes = new ArrayList<>();
        for (int i = 0; i < M; i++) boxes.add(sc.nextInt());

        // 크레인, 박스 모두 내림차순 정렬
        cranes.sort(Collections.reverseOrder());
        boxes.sort(Collections.reverseOrder());

        // 무거운 박스를 들 수 있는 크레인이 없으면 불가능
        if (boxes.get(0) > cranes.get(0)) {
            System.out.println(-1);
            return;
        }

        int time = 0;

        // 박스가 모두 없어질 때까지 반복
        while (!boxes.isEmpty()) {
            int boxIdx = 0;    // 현재 보고 있는 박스
            int craneIdx = 0;  // 현재 사용 중인 크레인

            // 1 분 동안 모든 크레인이 박스를 하나씩 옮김
            while (craneIdx < cranes.size()) {
                if (boxIdx >= boxes.size()) break;  // 박스 다 봤으면 종료

                if (cranes.get(craneIdx) >= boxes.get(boxIdx)) {
                    // 들 수 있는 박스 발견 → 바로 제거
                    boxes.remove(boxIdx);
                    craneIdx++;
                } else {
                    // 현재 크레인이 못 들면 더 가벼운 박스 탐색
                    boxIdx++;
                }
            }

            time++;
        }

        System.out.println(time);
    }
}