[백준/BOJ]11256. 사탕 [Silver 5]

11256. 사탕

문제출처 : https://www.acmicpc.net/problem/11256

code

#include <stdio.h>
void BubbleSort(int arr[],int num)
{
	int i, j, temp;
	for (i = num - 1; i > 0; i--)
		for (j = 0; j < i; j++)
			if (arr[j] < arr[j + 1])
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
}
int main()
{
	int T, N, J, R, C, box[1000], i, k, sum = 0, cnt = 0;
	scanf("%d\n", &T);
	for (i = 0; i < T; i++)
	{
		scanf("%d %d", &J, &N);
		for (k = 0; k < N; k++)
		{
			scanf("%d %d", &R, &C);
			box[k] = R * C;
		}
		BubbleSort(box, N);
		for (k = 0; k < N; k++)
		{
			sum += box[k];
			cnt++;
			if (sum >= J)
				break;
		}
		printf("%d\n", cnt);
		sum = 0;
		cnt = 0;
	}
	return 0;
}

계속 33%에서 틀렸다고 떠서 한참을 고민했는데, 출력을 T개의 줄로 출력해야하는데 한줄로 출력해서 틀렸던 것이였다......

이 문제도 알고리즘은 굉장히 쉽다.
테스트케이스를 입력받고,
테스트 케이스만큼 반복하는 반복문 안에서 사탕개수, 상자개수를 입력받고, 상자개수만큼 반복하는 반복문안에서 상자의 가로,세로크기를 입력받아 상자의 넓이배열에 저장하고, 상자의 넓이 배열을 소트한다. 왜냐하면 최소한의 상자를 써야하기 때문이다. 그리고 내림차순된 상자의 넓이를 하나씩 더하면서 sum의 크기가 사탕의 개수보다 많으면 반복을 그만두고 cnt을 출력한다. 그리고 테스트 케이스 반복을 하기전에 sum과 cnt는 초기화 해주어야 한다.