[BOJ] 2217로프 : 그리디 알고리즘 C++ 문제 해결 및 코드

---

이 문제가 왜 그리디 알고리즘인지 궁금해서 검색해봤다. 

그리디 알고리즘은 '최적의 답'을 찾는 것을 목적으로 하는데, 만약 입력값 즉 로프의 한계 중량이 50 90 100으로 나왔다고 치자. 첫번째 케이스로 50 90 100을 모두 사용하면 최대 중량은 150이고, 90 100만을 사용하면 180이다. 이렇게 50을 사용하지 않았을 경우 최적의 답을 낼 수 있어 그리디 알고리즘 문제라고 하는 것이다. 

 

문제 해결 과정은 이렇다.

/*
* 배열에 입력 숫자 넣고 오름차순 정렬
* list	 0  1  2
*       50 90 100
* 입력한 K값 즉 로프의 개수값에서 1씩 빼가며 다음 행동을 수행
* for(i는 0에서 k까지)
*	compare[k] = list[i] * k //list[3] = 150, list[2] = 180, list[1] = 100
*	k--;
* compare 배열의 max값을 반환
*/

algorithm헤더 파일의 sort함수와 max_element 요소를 이용해 문제를 해결하였다. 

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int list[100000]; //로프의 정보를 담을 배열
	int k; // 로프의 개수
	cin >> k;
	for (int i = 0; i < k; i++)
	{
		cin >> list[i];
	}
	sort(list, list + k); // 정렬
	int* compare = new int[k]; //메모리 크기가 k인 compare 배열 동적할당
	int temp = k; // temp = 3
	for (int i = 0; i < temp; i++) // 3번 반복
	{
		compare[k - 1] = list[i] * k; 
		//compare[2] = list[0] * 3 = 50 * 3 = 150
		//compare[1] = list[1] * 2 = 90 * 2 = 180
		//compare[0] = list[2] * 1 = 100 * 1 = 100
		k--;
	}
	cout << *max_element(compare, compare + temp) << endl;

	return 0;
}

뿌듯하군