[책 넣기]

[문제]

당신은 상자에 책을 넣고 있는데, 상자의 무게 제한을 넘지 않고 최대한 많이 넣어야 한다. 한 상자에 최대한 많이 책을 넣은 다음 상자를 닫고 봉인한 후, 다음 상자에 책을 넣을 수 있다. 책은 차곡차곡 쌓여있는데, 무조건 가장 위에서부터 책을 꺼내야 한다.

책들의 무게는 weights 로써 주어진다. 이 배열의 첫 번째 요소가 쌓여있는 책 중에서 가장 위에 있는 책이고, 배열의 마지막 요소가 가장 밑에 있는 책이다. 상자에 담을 수 있는 최대 무게는 maxWeight

로 주어진다. 책을 전부 담기 위한 상자의 최소 개수를 구하시오.

풀이 1) python

class Solution:
    def solution(self, weights, maxWeight):
        answer=[0]
        for i in weights:
            if answer[-1]+i>maxWeight:
                answer.append(i)
            else:
                answer[-1]+=i
        return len(answer) if answer[0]!=0 else 0

풀이 2) python

class Solution:
    def solution(self, weights, maxWeight):
        s=0
        t=0
        if len(weights)==0: return 0
        for w in weights:
            if s+w>maxWeight:
                t+=1
                s=w
            else:
                s+=w
        return t+1

풀이3) java

public class Solution{
    public int solution(int[] weights, int maxWeight){
        
        int temp = maxWeight;
        int answer=0;
        
        for(int i=0;i<weights.length;i++){
            if(i==0) answer+=1;
            if(temp>=weights[i]){
                temp-=weights[i];
            }else{
                temp=maxWeight-weights[i];
                answer++;
            }
        }
        
        return answer;
    }
}