Softeer-연습문제-택배 마스터 광우(C++)

문제 링크 :

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=581&sw_prbl_sbms_sn=41785

 

문제 개요 : 

 

일 해야하는 최소한의 무게 찾기

 

#include<iostream>
#include<algorithm>
#include<vector>

#define INF 1987654321

using namespace std;

int main(int argc, char** argv)
{
	// 입력
	int N,M,K;
	cin >> N >> M >> K;
	vector<int> rail(N);
	for(int i=0;i<N;i++){
		cin >> rail[i];
	}

	// 순열을 이용한 해결
	int res=INF; // 정답 저장할 변수
    sort(rail.begin(),rail.end()); // 오름차순 정렬
	do{
		int tmp_res=0,idx=0,k=0;
		while(k<K){ // K번 일하기
			int tmp_sum=0; // 이번에 들고 갈 무게 저장
			k++;
			while(tmp_sum + rail[idx] <= M){ // 들고 갈 무게 구하기
				tmp_sum += rail[idx];
				if(idx<N) idx++; // 다음 인덱스
				else idx=0; // 다음 인덱스
			}
			tmp_res += tmp_sum; // 전체 무게 구하기
		}
		if(tmp_res<res) res=tmp_res; // 무게 최솟값 구하기
	}while (next_permutation(rail.begin(),rail.end())); // 다음 조함 찾기

	// 결과 출력
	printf("%d",res);

	return 0;
}

 

문제 해결 방법

1. 순열을 이용하여 문제를 해결한다. (즉, 모든 경우에 수를 다 시도한다. aka 부르트포스)

2. 한 번에 들고 갈 무게를 구해서 tmp_sum에 저장하고 이를 tmp_res에 더하는 작업을 K번해서 총 무게를 구한다.

3. res와 tmp_res를 비교하여 더 작은 값을 res에 저장한다.

4. res를 출력하면 정답이다.