백준 1817 자바 - 짐 챙기는 숌 (BOJ 1817 JAVA)

문제 : boj1817

 

 

  '책은 탑처럼 차곡차곡 쌓여있기 때문에, 차례대로 박스에 넣을 수밖에 없다.' 부분이 없었다면 좀 더 어려웠을텐데, 이 문제의 경우 차례대로 넣을 수 밖에 없으므로 매번 최선의 선택만 진행하면 된다. (그리디 알고리즘)

 

  입력을 받으면서 M의 무게를 다 채울 때 까지 계속 진행하고, M이상이 되었다면 무게를 다시 리셋하고 박스의 개수를 올리는 방식을 모든 입력값에 대해 취하면 해결할 수 있다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        if (n == 0) {
            System.out.println(0);
            return;
        }

        st = new StringTokenizer(br.readLine());
        int capacity = m;
        int cnt = 1;
        while (n-->0) {
            int cur = Integer.parseInt(st.nextToken());
            if (capacity-cur>=0) capacity-=cur;
            else {
                cnt++;
                capacity = m-cur;
            }
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}