백준 1817 - 짐 챙기는 숌(자바 - 그리디)

https://www.acmicpc.net/problem/1817

1817번: 짐 챙기는 숌

 

* 문제 요약

숌은 짐을 챙겨서 겨울 캠프에서 집으로 가려고 한다.

그런데 공부를 많이 하러 캠프에 온것이기 때문에 책을 엄청나게 많이 가지고 왔다.

이 책을 방에 탑 처럼 쌓아놨다.

 

책을 박스에 차곡차곡 넣어서 택배로 미리 보내려고 한다.

책은 탑처럼 차곡차곡 쌓여있기 때문에 차례대로 박스에 넣을 수 밖에 없다.

각각의 책은 무게가 있다. 그리고 박스는 최대 넣을 수 있는 무게가 있다.

필요한 박스의 개수의 최소값을 구하는 프로그램을 작성하시오

 

* 입력

책의 개수 N 과 박스에 넣을 수 있는 최대 무게 M 이 주어진다.

N 은 0 보다 크거나 같고 50 보다 작거나 같은 정수이다.

M 은 1000 보다 작거나 같은 자연수이다.

N 이 0 보다 큰 경우 둘째 줄에 책의 무게가 공백을 사이에 두고 주어진다.

책의 무게는 M 보다 작거나 같은 자연수이다.

 

* 출력

필요한 박스의 개수의 최소값을 출력한다.

 

* 예시

 

* 해결 과정

책의 개수가 0 이라면 0 을 출력한다.

아닌 경우 다음과 같이 로직을 작성한다.

1. 책의 무게를 배열로 받아온다.

2. 매 반복마다 배열에서 현재 탐색중인 인덱스에 해당되는 값을 현재 무게 변수 currentWeight 에 더한다.

3. 현재 무게가 박스의 최대 중량 M 보다 작은 경우 다음 반복으로 넘어간다.

4. 현재 무게가 박스의 최대 중량 M 과 같은 경우 박스의 개수 변수 boxCount 에 1 을 더해주고 현재 무게 변수 currentWeight 를 0 으로 초기화해준다.

5. 현재 무게가 박스의 최대 중량 M 을 초과할 경우 현재 무게변수 currentWeight 를 현재 탐색한 책의 무게로 값을 초기화해준 다음 박스의 개수 변수 boxCount 에 1을 더해준다.

6. 반복이 끝난 이후에 currentWeight 변수에 0 이상인 값이 남아있다면 추가적으로 boxCount 에 1을 더해준다. 

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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[] inputArray = br.readLine().split(" ");

        int bookCount = Integer.parseInt(inputArray[0]);
        int boxWeight = Integer.parseInt(inputArray[1]);

        int currentWeight = 0;
        int boxCount = 0;

        if(bookCount == 0){
            bw.write("0");
        }
        else{
            String[] bookArray = br.readLine().split(" ");

            for(int i = 0; i < bookArray.length; i++){
                currentWeight += Integer.parseInt(bookArray[i]);

                if(currentWeight < boxWeight)
                    continue;
                else{
                    if(currentWeight == boxWeight){
                        currentWeight = 0;
                        boxCount++;
                    }
                    else if(currentWeight > boxWeight){
                        currentWeight = Integer.parseInt(bookArray[i]);
                        boxCount++;
                    }
                }
            }

            if(currentWeight > 0)
                boxCount++;

            bw.write(String.valueOf(boxCount));
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 단계에서의 선택이 다음 단계에 영향을 주지 않고, 각 단계별로 조건에 따라 최적의 선택을 하기 때문에

그리디 알고리즘 문제라고 할 수 있다.