[백준][C++] 2217 로프

2217. 로프

2217번: 로프

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

 

그리디에 대한 이해를 도와준 문제!

 

지금까지는 그리디 문제가 어색하고 감이 잘 잡히지 않았는데, 점점 그리디 문제를 풀어보니 완벽하지는 않지만... 그래도 감을 잡은 것 같다.

임의로 선택된 줄들이 버틸 수 있는 최대 무게를 계산하기 위해...

sort(weights.begin(), weights.end(), greater<int>());

먼저 내림차순으로 정렬해주었다. 내림차순으로 정렬한 이유는 반복문으로 계산할 때 증가하는 index 값인 i와 맞추기 편리했기 때문. 그 반복문은...

for (int i = 0; i < weights.size(); i++)
{
    // 버티는 최대 무게는 (무게/개수) =>
    // 최솟값 * 개수 
    int value = weights[i] * (i + 1);

    if (value > result)
    {
        result = value;
    }
}

이렇게 된다. 시뮬레이션을 돌리면

input => 3    5 9 1

// 정렬
=> 9 5 1

// 반복문
// 0   result = 9
// 1   reulst = 10 (MAX!)
// 2   result = 3

// answer
=> 10

 

전체 로직은 이렇다.

 

코드

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

int main()
{
	int count;
	int result = 0;
	vector<int> weights;

	cin >> count;

	for (int i = 0; i < count; i++)
	{
		int input;
		cin >> input;
		weights.push_back(input);
	}

	// 내림차순 정렬  
	sort(weights.begin(), weights.end(), greater<int>());

	for (int i = 0; i < weights.size(); i++)
	{
		// 버티는 최대 무게는 (무게/개수) =>
		// (i+1)개를 드는 것이므로
		// 버틸 수 있는 최대 무게 = (최대무게*(i+1)) 
		int value = weights[i] * (i + 1);

		if (value > result)
		{
			result = value;
		}
	}

	cout << result;
}

 

간단하지만 재미있는 문제였다!