백준 - 짐 챙기는 숌 ( 1817번, JAVA )

Greedy ( https://www.acmicpc.net/problem/1817 )

풀이

• 사실 이문제는 그리디보다 스택 문제다. 문제에 "책은 탑처럼 차곡차곡 쌓여있기 때문에, 차례대로 박스에 넣을 수 밖에 없다" 이말이 곧 후입선출을 가리키는 스택을 의미하기 때문에

package problem_solving.greedy;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class BaekJoon_1817 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.next());
		int m = Integer.parseInt(sc.next());
		int sum =  0 ; 
		
		Stack<Integer> st = new Stack<>();
		
		while(n-- > 0 ) {
			st.push(Integer.parseInt(sc.next()));
		}
		int cnt = 0 ; 
		while(!st.isEmpty()) {
			int weight = st.peek();
			if( sum + weight <= m ) {
				sum += weight;
				st.pop();
				if( st.isEmpty()) {
					cnt++;
				}
			} else {
				cnt++;
				sum = 0 ;
			}
		}
		
		
		System.out.println(cnt);
		
	}

}