[Softeer/C#]Level2 금고털이

https://softeer.ai/practice/info.do?idx=1&eid=395 

Softeer

문제

 

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

 

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

 

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

제약조건

1 ≤ N ≤ 106인 정수

1 ≤ W ≤ 104인 정수

1 ≤ Mi, Pi ≤ 104인 정수

입력형식

첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.

출력형식

첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

입력예제

100 2
90 1
70 2

출력예제

170

---

소스코드

 internal class Program
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(" ");

            int bagW = int.Parse(s[0].ToString());
            int kind = int.Parse(s[1].ToString());

            List<Tuple<int, int>> array = new List<Tuple<int, int>>();
            for (int i = 0; i < kind; i++)
            {
                string[] sSub = Console.ReadLine().Split(" ");

                array.Add(new Tuple<int, int>(int.Parse(sSub[0].ToString()), int.Parse(sSub[1].ToString())));
            }

            array.Sort((a,b) => b.Item2.CompareTo(a.Item2));

            int totalPrice = 0;
            for (int i = 0; i < array.Count; i++)
            {
               if( bagW > array[i].Item1)
                {
                    bagW -= array[i].Item1;
                    totalPrice += array[i].Item1 * array[i].Item2;
                }
                else
                {
                    totalPrice += bagW * array[i].Item2;
                }
            }
            Console.WriteLine(totalPrice);
        }
    }