1. 문제 정의
주어진 n개의 조약돌 중에서 m개의 조약돌을 꺼내려고 할 때, 어떤 조약돌을 꺼내는 것이 가장 좋은 선택인지 알아보는 문제입니다.
이 문제는 탐욕 알고리즘(Greedy Algorithm)을 사용하여 해결할 수 있습니다. 입력으로는 각 조약돌의 무게가 주어지며,
꺼낼 조약돌들의 총 무게가 최대 K가 되도록 해야 합니다.
2. 문제 이해
입력:
– 첫 번째 줄 : 조약돌의 개수 n (1 ≤ n ≤ 100)
– 두 번째 줄 : 꺼내야 할 조약돌의 개수 m (1 ≤ m ≤ n)
– 세 번째 줄 : 조약돌의 개수 n개에 대한 무게 (1 ≤ weight ≤ 1000)
출력:
– 꺼낸 조약돌들의 무게의 총합이 최대 K가 되도록 할 때, 그 총합을 구하라.
3. 예시
입력 예시:
5
3
1 2 3 4 5
출력 예시:
12 (3 + 4 + 5)
4. 알고리즘 설계
이 문제를 해결하기 위해서는 우선 주어진 조약돌의 무게를 정렬한 후, 가장 무거운 조약돌부터 m개를 선택하는 과정을 거쳐야 합니다.
이때, 선택된 조약돌의 총 무게를 계산하여 결과를 출력합니다. 알고리즘의 단계는 다음과 같습니다.
- 조약돌의 무게를 오름차순으로 정렬한다.
- 정렬된 조약돌의 마지막 m개를 선택한다.
- 선택된 조약돌의 무게를 합산하여 결과를 출력한다.
5. 코드 구현
이제 위의 알고리즘을 바탕으로 C++ 코드를 구현해보겠습니다.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int n, m;
std::cout << "조약돌의 개수를 입력하세요: ";
std::cin >> n;
std::cout << "꺼내야 할 조약돌의 개수를 입력하세요: ";
std::cin >> m;
std::vector<int> weights(n);
std::cout << "조약돌의 무게를 입력하세요 (띄어쓰기로 구분): ";
for (int i = 0; i < n; ++i) {
std::cin >> weights[i];
}
// 조약돌 무게 정렬
std::sort(weights.begin(), weights.end());
// 가장 무거운 m개 조약돌 선택
int total_weight = 0;
for (int i = n - m; i < n; ++i) {
total_weight += weights[i];
}
std::cout << "선택된 조약돌의 총 무게: " << total_weight << std::endl;
return 0;
}
6. 코드 설명
위의 C++ 코드는 주어진 조약돌의 개수와 선택해야 하는 조약돌의 개수를 입력받고, 각 조약돌의 무게를 배열에 저장합니다.
그런 다음, STL의 sort 기능을 사용하여 무게를 정렬합니다. 정렬된 배열에서 가장 무거운 m개를 선택하여 총 무게를 계산하고 출력합니다.
7. 알고리즘 복잡도 분석
이 알고리즘의 시간 복잡도는 조약돌의 개수를 n이라고 할 때, O(n log n)입니다. 정렬 과정이 가장 큰 비중을 차지합니다.
공간 복잡도는 O(n)이며, 이는 입력으로 받은 조약돌의 무게를 저장하기 위해 필요한 메모리입니다.
8. 문제 해결 후기
이 문제는 탐욕 알고리즘의 기초를 배우기에 적합한 연습 문제입니다. 조약돌을 꺼내는 문제를 통해
최적화된 선택을 할 수 있는 방법을 익힐 수 있습니다. 실제 코딩 테스트에서도 유사한 형태의 문제가 자주 출제되므로
반복적인 연습이 필요합니다. 앞으로 다양한 문제를 풀어보면서 더 많은 경험을 쌓아가시길 바랍니다.