[알고리즘 PS] 백준 1434번 책 정리 자바 문제풀이

문제

해당 포스팅은 백준의 1434번 책 정리 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

1434번: 책 정리

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

이 문제는 그리디 문제로 2가지 방식으로 풀 수 있다.

1. 시간 복잡도 n 으로 풀기
2. 시간 복잡도 1 로 풀기

우선 시간 복잡도 n으로 푸는 방법을 봐보자.

시간 복잡도 N

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] nm = br.readLine().split(" ");
        String[] boxesStr = br.readLine().split(" ");
        String[] booksStr = br.readLine().split(" ");
        int n = Integer.parseInt(nm[0]);
        int m = Integer.parseInt(nm[1]);

        int[] boxes = new int[n];
        int[] books = new int[m];

        for (int i = 0; i < n; i++) {
            boxes[i] = Integer.parseInt(boxesStr[i]);
        }

        for (int i = 0; i < m; i++) {
            books[i] = Integer.parseInt(booksStr[i]);
        }

        int answer = 0;
        int i = 0, j = 0;
        while(true) {
            if(j == books.length) break;
            int value = boxes[i] - books[j];
            if(value >= 0) { // 박스가 충분하면
                boxes[i] = value;
                j++;
            }else { // 박스가 모자라면
                i++;
            }
        }

        for(int value : boxes) {
            answer += value;
        }
        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }
}

이렇게 하나의 책이 채워지고 박스와 비교를 한 뒤, 박스가 더 크면 책을 담고 더 작으면 다음 박스로 이동하는 방식이다.

그리고 최종적으로 박스에 남은 용량을 합산해주면 된다.

시간 복잡도 1

public class Main {
    public static void main(String[] args) throws IOException {

        // 입력 과정 생략

        int bookSum = 0;
        int boxSum = 0;

        for(int value : boxes) boxSum += value;
        for(int value : books) bookSum += value;
        bw.write(String.valueOf(boxSum - bookSum));
        bw.flush();
        bw.close();
    }
}

혹은 이와 같이 모든 박스의 용량에서 책의 용량을 빼도 해결할 수 있게 된다.

그 이유는 조건에서 보면

문제에 주어진 방법으로 모든 책을 박스에 넣을 수 있는 경우만 입력으로 주어진다.

라고 했기 때문에 이와 같이 풀 수 있는 것이다.

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.