[Softeer] 택배 마스터 광우 (C++)
문제
여름 휴가를 떠나기 위해 용돈이 필요했던 광우는 H택배 상하차 아르바이트를 지원했다. 광우는 평소에 운동을 하지 않아 힘쓰는 데에 자신이 없었지만, 머리 하나 만큼은 비상해 택배가 내려오는 레일의 순서를 조작해서 최소한의 무게만 들 수 있게 일을 하려고 한다.
레일은 N개이며, 각각의 레일은 Ni무게 전용 레일로 주어진다. (같은 무게의 레일은 주어지지 않는다.) 레일의 순서가 정해지면 택배 바구니 무게(M)를 넘어가기 전까지 택배 바구니에 택배를 담아 들고 옮겨야 한다. 레일 순서대로 택배를 담되, 바구니 무게를 초과하지 않은 만큼 담아서 이동하게 되면 1번 일한 것으로 쳐준다. (단, 택배는 순서대로 담아야 하므로 레일의 순서를 건너 뛰어 담을 수는 없다.)
총 K번 일을 하는데 최소한의 무게로 일을 할 수 있게 광우를 도와주는 프로그램을 만들어 보자.
제약 조건
입력 형식
첫째 줄에는 레일의 개수 N, 택배 바구니의 무게 M, 일의 시행 횟수 K가 주어진다. 그 다음 줄에는 Ni개의 택배 레일의 전용 무게가 주어진다. (택배 바구니는 무조건 택배보다 작은 경우는 없다.)
출력 형식
출력으로는 광우가 일 해야하는 최소한의 택배 무게를 출력한다.
입력 예시 1
5 20 4
5 8 10 19 7출력 예시 1
54입력 예시 2
9 25 50
1 21 2 22 3 23 4 24 10출력 예시 2
772문제의 의도
문제의 의도는 레일의 배치 순서를 바꿔 바구니들을 최소한의 무게로 적재할 수 있는 최적의 배치를 찾도록 코드를 작성하는 것이다.
접근법
주어진 레일의 배치 순서를 순열 방식을 사용하여 가능한 모든 배치 순서를 탐색한 후, 각 배치에서 바구니를 적재하여 그 무게를 계산하고, 최적을 결과를 찾는다. N의 범위가 크지 않기 때문에 충분히 순열 알고리즘으로 해결이 가능하다. 그러나, N이 클 경우에는 시간초과가 발생할 수 있다.
C++ 구현 코드
핵심 아이디어는 다음과 같다.
- 순열 생성(permutation 함수)
- rails_w에 저장된 레일의 무게 제한 백테에 대해 모든 가능한 순열을 생성한다.
- 순열이 완성될 때마다, 해당 순열로 바구니를 적재해보고 무게를 계산한다.
- 무게 계산(computeAns 함수)
- 생성된 순열에서 바구니를 적재할 때의 총 무게를 계산하는 함수이다.
- 각 레일에 바구니를 차례대로 적재하며, 레일의 최대 무게(m)를 초과하지 않도록 한다.
- 바구니의 무게가 레일의 제한을 넘으면 다음 레일로 넘어간다.
- 각 순열에서 계산된 무게를 최소값으로 갱신하여 최적의 결과를 찾는다.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n, m, k;
int ans = 100000;
void computeAns(vector<int> rails_w) {
int bucket = 0, total = 0, idx = 0;
for (int i=0; i<k; i++) {
while (bucket+rails_w[idx]<=m) {
bucket += rails_w[idx];
idx = (idx + 1) % n;
}
total += bucket;
bucket = 0;
}
ans = ans < total? ans:total;
}
void permutation(vector<int> rails_w, int loc) {
if (loc == n-1) {
computeAns(rails_w);
return;
}
for (int i=loc; i<n; i++) {
swap(rails_w[loc], rails_w[i]);
permutation(rails_w, loc+1);
swap(rails_w[loc], rails_w[i]);
}
}
int main(int argc, char** argv)
{
cin >> n >> m >> k;
vector<int> rails_w(n);
for (int i=0; i<n; i++) {
cin >> rails_w[i];
}
permutation(rails_w, 0);
cout << ans << endl;
return 0;
}