문제 요약

[2217] 로프

로프에 대한 정보가 주어질 때 로프들을 선택적으로 사용하여 물체를 들 수 있는 최대 무게를 계산하는 문제

풀이 과정

로프가 견딜 수 있는 최대 무게가 큰 로프를 먼저 선택하는 것이 합리적임. (최대한 무거운 물체를 들어 올리는 것이 목표이므로)

따라서 들 수 있는 최대 무게를 계산하여 매 순간의 최대값을 저장해두었다가 무게가 감소하는 시점에 탐색을 종료하고 저장해둔 최대값을 출력한다.

코드 (C/C++)

1. 각 로프가 견딜 수 있는 최대 무게를 내림차순으로 정렬
2. 튼튼한 로프 순으로 선택하여, 이 기계가 들 수 있는 최대 무게를 계산 후 저장
3. 계산한 무게가 이전과 비교했을 때 감소하는 경우, 로프를 선택하지 않고 종료

비교함수

• 1, 0, -1 중에 하나를 반환
• 오름차순으로 정렬한다면 (내림차순인 경우 등호 바꿔서)
  * 첫번째 변수 > 두번째 변수 => 1
  • 첫번째 변수 < 두번째 변수 => -1
  • 첫번째 변수 = 두번째 변수 => 0

//언어 cpp, 메모리 1896KB, 시간 24ms
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(const void * first, const void * second)
{
	if (*(int*)first > *(int*)second) return -1;
	else if (*(int*)first < *(int*)second) return 1;
	else return 0;
} //내림차순 정렬

int main(void)
{
	int n;
	int * rope;
	int w; //최대중량
	scanf("%d", &n); //로프의 개수
	rope = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &rope[i]);
	} //로프가 견딜 수 있는 최대 중량
	//정렬할 배열, 배열 총 개수, 배열 원소 하나 크기, 비교 수행 함수 포인터
	qsort(rope,  n, sizeof(int), compare);
	w = rope[0];
	for (int i = 1; i < n; i++)
	{
		if (w < (rope[i] * (i + 1)))
		{
			w = rope[i] * (i + 1);
		}
	}
	printf("%d\n", w);
}