[백준/BOJ]2217. 로프 [Silver 4]

2217. 로프

문제출처 : https://www.acmicpc.net/problem/2217

로프 사이즈와 로프의 갯수를 동시에 생각해야하기 때문에 조금 복잡한 알고리즘이였지만,
사이즈와 갯수에 얽매이지 않는다면 정말 간단하게 짤 수 있었다. 코드도 보다시피 대부분은 퀵정렬 코드이고, 진짜 코드는 반복문 하나밖에 안된다.

code

#include <stdio.h>
void QuickSort(int *arr,int start,int end)
{
	if (start >= end)
		return;
	int piv = start;
	int left = start + 1, right = end, temp;
	while (left <= right)
	{
		while (left <= end && arr[left] >= arr[piv])
			left++;
		while (right > start && arr[right] <= arr[piv])
			right--;
		if (left > right)
		{
			temp = arr[right]; arr[right] = arr[piv]; arr[piv] = temp;
		}
		else
		{
			temp = arr[left]; arr[left] = arr[right]; arr[right] = temp;
		}
	}
	QuickSort(arr, start, right - 1);
	QuickSort(arr, right + 1, end);
}
int main()
{
	int N, i, rope[100000] = { 0 }, w = 0;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d", &rope[i]);
	QuickSort(rope, 0, N - 1);//내림차순
	w = rope[0];
	for (i = 1; i < N; i++)
	{
		if (w < rope[i] * (i+1))
			w = rope[i] * (i+1);
	}
	printf("%d", w);
	return 0;
}

입력받은후, 로프배열을 내림차순으로 정렬한다.
그다음 반복문을 돌면서(돌때마다 로프의 갯수가 추가된다.) 총 들수 있는 중량을 구하는데,
로프가 몇개든 들수있는 무게는 로프중 가장 약한로프에 초점을 맞추기 때문에
(가장 약한로프 X 로프의 갯수)로 총중량을 구한다. (어차피 내림차순정렬해서 제일 최신인덱스가 가장 약한로프임) 그리고 그 총중량이 저번인덱스 때 구한 총중량보다 크면 w를 최신화하고, 작으면 무시.
반복문이 끝나면 w를 출력한다.