문제풀이(61)

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

import java.util.*;
import java.io.*;


public class Main {

    static int n,m;
    static Deque<Integer>dp = new ArrayDeque<>();

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());

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

        m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
    
            dp.offerLast(Integer.parseInt(st.nextToken()));
        }

        

        int cnt = 0;

        int sum = m;

        while (!dp.isEmpty()) {
            
            if (sum - dp.peekFirst() < 0) {
                
                cnt++;
                sum = m;
                continue;
            }

            sum-=dp.pollFirst();
        }

        System.out.println(cnt+1);
    }
}

문제풀이방법
문제를 분석해보면 < "책은 탑처럼 차곡차곡 쌓여있기 때문에, 차례대로 박스에 넣을 수밖에 없다." > 이런 문장이 나온다. 나는 여기에서 앞,뒤에서 데이터를 꺼내고 넣을 수 있는 deque 자료구조를 사용해야 겠다고 생각했다. 그런데 문제를 풀고 보니까 Queue를 사용해도 충분히 해결 할 수 있는 문제였다. 우선 첫번째로 m 값을 변수 sum에 넣어준다 그 다음에 while 문을 돌면서 deque에 있는 데이터를 앞에서 부터 하나씩 꺼내면서 최대 넣을수 있는 무게인 sum에 꺼낸 값을 빼준다. 그러다가 sum이 0보다 작아지는 순간이오면 cnt 값을 하나 증가시키고 변수 sum은 다시 처음 값인 m을 대입 시킨다. 이런 과정을 반복하면서 deque가 Empty가 되면 while 반복문을 끝낸다.