(C++) - 백준(BOJ) 1817 : 짐 챙기는 숌

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

1817번: 짐 챙기는 숌

greedy 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

책 개수 bookNum, 박스에 넣을 수 있는 최대 무게 maxWeight, 정답을 출력할 answer, 박스에 책을 넣는 현황을 비교할 sum, 책들의 무게 정보 vector booksWeight를 선언 후 적절히 입력받습니다.

📔 풀이과정

책의 무게를 오름차순으로 정렬하면 더 적은 박스를 사용할 수 있지만 문제조건 책은 탑처럼 차곡차곡 쌓여있기 때문에, 차례대로 박스에 넣을 수밖에 없다. 으로 인해 불가능합니다.

1. booksWeight정보를 차례대로 확인합니다.

2. 이후 while loop를 수행합니다.

  2-1. maxWeight이하까지 sum변수에 책들을 넣는다는 의미로 값을 누적해 더해줍니다.

  2-2. maxWeight를 넘는 순간의 index의 이전을 pivot에 저장해주고 break해줍니다.

3. 박스가 버틸 수 있는 최대 무게까지 책을 넣었으므로 박스 1개를 사용했다는 의미로 answer++해줍니다.

📔 정답출력

answer를 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;

int bookNum, maxWeight, answer, sum;
vector <int> booksWeight;

int main(){
  cin >> bookNum >> maxWeight;
  booksWeight.resize(bookNum);

  for(int i = 0; i < bookNum; i++){
    cin >> booksWeight[i];
  }

  for(int i = 0; i < booksWeight.size(); i++){
    int pivot = i, sum = 0;
    while(1){
      sum += booksWeight[pivot];
      if(sum > maxWeight) {
        pivot--; 
        break;
      }
      pivot++;
    }
    i = pivot;
    answer++;
  }
  cout << answer;
}

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.