[C#] 백준 2217번 문제풀이

문제번호: 2217

문제명: 로프

문제링크: https://www.acmicpc.net/problem/2217

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다

안녕하세요. 오늘은 그리디 알고리즘을 사용한 수학문제인 로프 문제를 풀었습니다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다라는 공식을 사용하여 로프로 들 수 있는 최대 무게를 구하는 문제입니다. 핵심 아이디어는 다음과 같습니다.

각 로프가 버텨야할 하중은 W/k <= 각로프의최대하중 입니다. 여기서 가장 약한 로프의 최대하중을 min이라 할 때 W/k <= min이고, 양변에 k를 곱하면 W <= min * k라는 공식이 나오게됩니다. 따라서 로프를 순회하며 W <= ropes[i] * k공식을 계산하여 max값과 비교하여 더 큰수를 max에 갱신시켰습니다.
다음은 정답코드입니다.

 

public static void Main()
{
    using StreamReader sr = new StreamReader(Console.OpenStandardInput());
    using StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int n = int.Parse(sr.ReadLine());
    List<int> ropes = new List<int>();
    for (int i = 0; i < n; i++)
        ropes.Add(int.Parse(sr.ReadLine()));
    ropes.Sort();

    int maxNum = 0;

    for (int i = 0; i < n; i++)
    {
        maxNum = Math.Max(maxNum, ropes[i] * (n - i));
    }

    sw.WriteLine(maxNum);

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

    // 각 로프가 버텨야할 하중: W/k <= 각로프의최대하중
    // 가장 약한 로프의  최대하중을 min이라고 하면 W/k <= min
    // 양변에 k를 곱하면 W <= min * k
}