[백준] 짐 챙기는 숌 - c++

1817

문제

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

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

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

입력

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

출력

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

예제

문제 정의

문제에서 다음과 같은 조건이 있다.

책은 탑처럼 차곡차곡 쌓여있기 때문에, 차례대로 박스에 넣을 수밖에 없다.

따라서 차례로 현재 책의무게와 아래에 책의 무게를 합친 값이 최대 무게 M보다 작거나 같으면 계속해서 누적 무게를 더한다. 현재 책의무게와 아래에 책의 무게를 합친 값이 M을 초과하는 경우는 지금까지의 책은 박스에 담아야 하니 박스개수를 하나 더하고 현재 책의 무게까지 넣으면 초과되므로 넣지 못하여 누적무게값에 현재 책의 무게가 저장된다.

이 과정을 반복하고 난 후, 누적 무게값이 0보다 크고 m 보다 작은경우 이 책들을 모두 한 박스에 넣어야 되므로 박스 개수 +1을 해주면 된다.

코드

#include<bits/stdc++.h>

using namespace std;

int n, m, ans;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> n >> m;
  vector<int> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }

  int sum = 0;
  for (int i = 0; i < n; i++) {
    if (v[i] + sum <= m) {
      sum += v[i];
    } else {
      ans++;
      sum = v[i];
    }
  }

  if (sum > 0)
    ans++;
  cout << ans << endl;

  return 0;
}