BaekJoon 2217번: 로프

풀이법

1) 그리디 접근법을 사용하면 쉽게 풀 수 있는 문제이다.

2) 내림차순으로 배열을 정렬한 후 하나씩 넣어보며 최대값을 비교한다면 어렵지 않게 풀 수 있을 것이다.

#include <algorithm>
using namespace std;

int n;
vector<int> arr;
long long ans=0;
bool compare(int a, int b)
{
	if (a <= b)
	{
		return false;
	}
	else
		return true;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		arr.push_back(a);
	}
	sort(arr.begin(), arr.end(),compare);
	for (int i = 0; i < n; i++)
	{
		int temp;
		temp = arr[i] * (i + 1);
		if (ans <= temp)
		{
			ans = temp;
		}
		
	}
	cout << ans<<"\n";
}

한계점 및 개선사항 (+주의사항)

main함수에서 최대값을 찾는 for문에 if(ans>temp) break를 넣게 되면 틀리는 부분을 신경써야 한다.

[15, 10, 7, 5, 5]가 그 반례이다.

올려둔 source 코드에 기반하면

15->20->21->pass->25가 되어 값이 25가 출력되어 정답임을 알 수 있다.

허나 ans>temp일 경우 break를 해버리면

15->20->21에서 break가 되어 잘못된 값을 출력할 수 있으니 주의해야 한다.

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest