BOJ 9550 - 아이들은 사탕을 좋아해

문제

N개의 사탕 봉지가 있고 각 봉지에 사탕이 들어 있다. 각 아이에게 K개씩 나누어 줄 때, 최대 몇 명에게 줄 수 있는지 구하라.

입력

테스트 케이스 수 T, 각 케이스에 봉지 수 N과 K, 이후 각 봉지의 사탕 수가 주어진다.

출력

각 케이스마다 최대 아이 수를 출력한다.

예제

입력	출력
`1` `3 2` `4 7 3`	`7`

풀이

각 봉지에서 K개씩 줄 수 있는 아이 수를 합산한다.

각 봉지의 사탕 수를 K로 나눈 몫을 구한다
모든 봉지의 몫을 합산하면 총 나눠줄 수 있는 아이 수가 된다

핵심 아이디어: 봉지 간 사탕을 섞지 못하므로, 각 봉지에서 독립적으로 candy / K를 계산하여 합산한다.

코드

#include <iostream>
 
using namespace std;
 
int t, n, k, candy, result;
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> t;
  while (t--)
  {
    cin >> n >> k;
    result = 0;
    for (int i = 0; i < n; i++)
    {
      cin >> candy;
      result += candy / k;
    }
    cout << result << "\n";
  }
  return 0;
}

복잡도

시간: O(N)
공간: O(1)

문제