[BOJ / C++] 1817번 : 짐 챙기는 숌

문제

숌은 짐을 챙겨서 겨울캠프에서 집으로 가려고 한다. 근데 숌은 공부를 많이 하러 캠프에 온 것이기 때문에 책을 엄청나게 많이 가지고 왔다. 숌은 이 책을 방에 탑처럼 쌓아 놨다.

숌은 책을 박스에 차곡차곡 넣어서 택배로 미리 보내려고 한다. 책은 탑처럼 차곡차곡 쌓여있기 때문에, 차례대로 박스에 넣을 수밖에 없다.

각각의 책은 무게가 있다. 그리고 박스는 최대 넣을수 있는 무게가 있다. 숌이 필요한 박스의 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 50보다 작거나 같은 정수이고, M은 1,000보다 작거나 같은 자연수이다. N이 0보다 큰 경우 둘째 줄에 책의 무게가 공백을 사이에 두고 주어진다. 책의 무게는 M보다 작거나 같은 자연수이다.

출력

첫째 줄에 필요한 박스의 개수의 최솟값을 출력한다.

Solved.ac 레벨

실버 V

풀이

#include <bits/stdc++.h>

using namespace std;

int n, m, ans, tmpSum;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    for(int i = 0; i < n; i++){
        int weight;
        cin >> weight;
        tmpSum += weight;

        if(tmpSum > m){
            ans++;
            tmpSum = weight;
        }
    }

    if(tmpSum != 0){
        ans++;
    }


    cout << ans << '\n';

    return 0;
}

이 문제는 그리디처럼 보여서 입력을 받으면서 우선순위 큐에 넣어 내림차순으로 정렬 후, 큰 값들 먼저 넣어보는 방법으로 접근했었는데, 어쨌든 박스의 최대값만 채우면 되니 입력을 받으면서 박스에 다 넣어보는 방식으로 풀었다.

 

출력하기 전에 다시 한 번 박스 개수를 증가시켜주는건 상자에 책을 넣지 않는 경우 (마지막 예제)를 고려한 것이다. 사실 고려를 했다기 보다는 예제를 넣어보면 출력이 1씩 작아서... 해봤는데 맞았다...(?)

 

1817번: 짐 챙기는 숌