JArchive 프로그래밍 일기

택배 마스터 광우 문제 링크 

리뷰 

택배를 담을 때 레일을 스킵할 수 없음에 주의해야 한다. 

모든 레일의 순서 조합을 검사해야 한다. -> next_permutation() 은 정렬된 자료구조의 모든 순열을 리턴해준다. 

현재 레일까지의 합이 무게제한을 초과한다면, 직전 레일에서 담은 택배까지가 1개의 바구니에 꽉찬 것이다.

따라서 일한 횟수를 1 증가 시키고,  바구니 무게를 0으로 비우면 된다. 

현재 레일까지의 합이 무게제한 범위 내라면,  현재 바구니에 택배를 담는다. 총 누적 무게에도 택배 무게를 증가시킨다. 

일한 횟수 cnt가 목표 횟수 k 번을 만족하면, 총 누적 무게가 최소인지 비교한다. 

맞았습니다 코드 

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

int n, m, k; // 레일 개수, 바구니 무게, 일의 개수
int answer = 2e9;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m >> k;
  vector<int> rail(n, 0);

  for(int i = 0; i < n; i++)  cin >> rail[i];
  sort(rail.begin(), rail.end()); // 레일을 오름차순 정렬 

  do{
     // 종료한 일의 개수, 누적 무게, 현재 바구니 무게, 레일 인덱스
    int cnt = 0, sum = 0, temp = 0, idx = 0; 

    while(cnt < k){ // 일을 총 k번 해야 한다. 
      temp = 0; // 현재 바구니의 무게 0 
      
      while(temp + rail[idx] <= m){
        temp += rail[idx];
        sum += rail[idx];
        idx = (idx + 1) % n; // 레일 인덱스 증가. 레일은 최대 n개니까 %n 해준다. 
      }
      cnt++; // 종료한 일의 개수 증가시킨다. 
    }
    answer = min(sum, answer); // 무게 합이 최소인지 비교 
    
  }while(next_permutation(rail.begin(), rail.end())); // 레일의 모든 순열 만들기 

  cout << answer;
  return 0;
}

제출 기록