[알고리즘 문제 풀기] 사탕(11256)

1. 문제 풀이 아이디어

• 배열 정렬을 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

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

int t = int.Parse(sr.ReadLine());
for (int i = 0; i < t; i++)
{
    string[] split = sr.ReadLine().Split();
    int j = int.Parse(split[0]);
    int n = int.Parse(split[1]);
    int[] arr = new int[n];
    for (int k = 0; k < n; k++)
    {
        split = sr.ReadLine().Split();
        arr[k] = int.Parse(split[0]) * int.Parse(split[1]);
    }
    Array.Sort(arr);
    int sum = 0;
    for (int k = 0; k < n; k++)
    {
        sum += arr[n - k - 1];
        if (sum >= j)
        {
            sw.WriteLine(k + 1);
            break;
        }
    }
}

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

3. 정리

• 여러 테스트 케이스를 처리하기 위해 for (int i = 0; i < t; i++) 루프를 사용한다.

• arr[k]에는 각 상자의 사탕 개수를 저장한다.

• Array.Sort(arr)로 정렬한 후, 큰 값부터 선택하기 위해 n - k - 1 인덱스를 사용한다.

• sum 변수를 이용하여 사탕 개수를 누적하며, sum >= j가 되면 반복을 종료하고 상자의 최소 개수를 출력한다.