나의, 코딩 일기

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

조건 및 입출력

- 첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

- 첫째 줄에 답을 출력한다.

- 시간 제한: 2초 이내 / 메모리 제한: 192MB 이내

코드 (C99)

#include <stdio.h>

//프로토타입 선언부
void heap_sort(int heap[], int size);

//전역변수 선언부
int rope[100000] = { 0 };

main()
{
	int test, result = 0;
	scanf("%d", &test);

	for (int i = 0; i < test; i++)
		scanf("%d", &rope[i]);

	heap_sort(rope, test);
	// 수식 일반화 -> w=n*k


	for (int i = 0; i < test; i++)
	{
		if (result < (test - i) * rope[i])
			result = (test - i) * rope[i];
	}

	printf("%d\n", result);

	return 0;
}

void heap_sort(int heap[], int size)
{
	for (int i = 1; i < size; i++)
	{
		int child = i;
		do
		{
			int root = (child - 1) / 2;
			if (heap[root] < heap[child])
			{
				int temp = heap[root];
				heap[root] = heap[child];
				heap[child] = temp;
			}
			child = root;
		} while (child != 0);
	}

	for (int i = size - 1; i >= 0; i--)
	{
		int temp = heap[0];
		heap[0] = heap[i];
		heap[i] = temp;
		int root = 0;
		int child = 1;
		do
		{
			child = 2 * root + 1;

			if (child < i - 1 && heap[child] < heap[child + 1])
				child++;
			if (child < i && heap[root] < heap[child])
			{
				temp = heap[root];
				heap[root] = heap[child];
				heap[child] = temp;
			}
			root = child;
		} while (child < i);
	}
}

여담

문제 이해하는 것부터가 어려움이었다.

도르래 원리를 이용하여 문제를 푸는 건 줄 알았는데, 그게 아니었다.

천장에 물체를 메달아 놓는다는 개념으로 접근해야 할 것이다.

처음에 줄의 갯수가 주어진다. 그리고 그 수만큼 값을 입력받는다.

여러개의 로프로 병렬 연결하면 로프에 걸리는 중량을 나눌 수 있다.

모든 로프에 같은 힘이 작용해야 돌림힘에 의해 돌아가지 않을 것이다.

고로, 가장 약한 로프를 하나 선택한 뒤 병렬로 연결하면 들어올릴 수 있는 최대의 중량이 나올 것이다.

이 개념을 바탕으로 코드로 구현하면,

제일 우선 가장 작은 값을 찾기 위해 정렬을 수행한다.

나는 힙 정렬로 배열에 있는 모든 값을 정렬하였다. 그 후 로프 힘이 작은 순서 * 총 로프 개수를 곱해가며 최대의 힘을 낼 수 있는 경우를 찾아 결과로 출력하면 정답이다.