[백준] 2217 - 로프

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

int main()
{
    int n, count, r[100001];
    
    cin >> n;
    
    for (int i = 0; i < n; i++)
    {
        cin >> r[i];
    }
    
    sort(r, r + n);

    for (int i = 0; i < n; i++)
    {
        r[i] = r[i] * (n - i);
    }
    sort(r, r + n);
    cout << r[n-1]; 
}

이번 문제는 로프에 개수와 무게를 곱한 값이 가장 큰 값이 정답입니다. 

만약 총 로프의 개수(n)이 4 라고 하고 로프가 견딜수 있는 무게들의 값이

15

20

25

30

이라고 한다면 

15 * 4 = 60

20 * 3 = 60

25 * 2 = 50

30 * 1 = 30 이 됩니다.

정답은 가장 큰 무게인 60이 나옵니다.

---

다른 사람의 코드를 보겠습니다.

#include<iostream>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int cache[10001] = { 0 };
	int n,i; cin >> n;
	for (i = 0; i < n; i++)
	{
		int tmp; cin >> tmp;
		cache[tmp]++;
	}
	long long max = -1;
	int total = n;
	for (i = 1; i <= 10000; i++)
	{
		if (cache[i] > 0)
		{
			if (max < i*total)
			{
				max = i * total;
			}
			total -= cache[i];
		}
	}
	cout << max;
}

입력된 숫자의 주소에 1을 더하여 존재 여부만 알리는 배열 "cache"를 만들고 for문을 돌면서 만약 배열에 인덱스 i 위치에 값이 있다면 그 값은 i  가 됩니다. 그리고 max 값에  i * 로프의 개수를 더하고 total -= 1 을 해줘서 로프의 개수를 줄이는 방식으로 구현하셨습니다. 

전반적인 알고리즘의 개념은 같지만 구현 방식에서 차이가 납니다.

시간도 이분이 32 ms 빠르고 메모리도 72kb 적습니다.

우선 시간이 더 빠른 이유는 

ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL); 

를 사용해서 이고 

메모리는 

#include <algorithm> 을 사용하지 않고 풀어서 그런 것 같습니다.