백준알고리즘 2217번 로프 C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 2217
• 문제명: 로프
• 언어: C#
• 분류: 수학, 그리디 알고리즘, 정렬
• 비고: 

 

문제

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

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

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

 

입력

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

 

출력

첫째 줄에 답을 출력한다.

 

풀이

로프 무게를 낮은 순으로 정렬하고, 무게에 (로프 개수 - 1)을 곱하면 최대 하중이 나온다.

이후 들 수 있는 무게가 낮은 로프를 빼면서 들 수 있는 최대 하중을 구하면 된다.

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

// 로프의 개수 입력
int n = Convert.ToInt32(sr.ReadLine());
// 로프별로 들 수 있는 최대 무게
int[] rope = new int[n];
// 여러 개의 로프를 사용했을 때 들 수 있는 최대 무게
int maxWeight = 0;

// 로프별로 들 수 있는 최대 무게 입력
for (int i = 0; i < rope.Length; i++)
    rope[i] = Convert.ToInt32(sr.ReadLine());

// 로프별로 들 수 있는 최대 무게가 낮은 순대로 정렬
Array.Sort(rope);

// 로프 최대 하중은 무게 * (로프 개수 - i)다
for (int i = 0; i < rope.Length; i++)
    maxWeight = Math.Max(maxWeight, rope[i] * (n - i));

// 로프 최대 하중 출력
sw.WriteLine(maxWeight);

sr.Close();
sw.Close();

 

후기

피드백을 통해 푸는 방법을 알게 된 이상 이것도 외워두기로 하겠다. 풀기 전에는 아무래도 로프를 연결해 물체를 들어올리는 경우 최대 하중을 계산하려면 물리학 지식이 필요하다고 보았다. 이러한 유혀의 문제는 또 없는 걸까?