BOJ 13304 - 방 배정

문제

학생들을 성별과 학년 기준으로 그룹으로 나눈 뒤, 각 그룹에서 K명씩 한 방에 배정할 때 필요한 최소 방 수를 구하라.

입력

학생 수 N과 방 최대 인원 K, 이후 각 학생의 성별과 학년이 주어진다.

출력

필요한 최소 방 수를 출력한다.

예제

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

풀이

학생을 5개 그룹으로 분류하고, 각 그룹별 방 수를 올림 나눗셈으로 구한다.

학년과 성별에 따라 5개 그룹(저학년, 남고, 여고, 남대, 여대)으로 분류한다
각 그룹의 인원을 K로 나누어 올림한다
모든 그룹의 방 수를 합산하여 출력한다

핵심 아이디어: 같은 그룹끼리만 같은 방을 쓸 수 있으므로, 그룹별로 독립적으로 방 수를 계산하면 된다.

코드

#include <iostream>
using namespace std;
 
int n, k, q, w, a[5];
int main()
{
  cin >> n >> k;
  while (n--)
  {
    cin >> q >> w;
    if (w < 3)
      a[0]++;
    else if (w < 5)
      if (q)
        a[1]++;
      else
        a[2]++;
    else if (q)
      a[3]++;
    else
      a[4]++;
  }
  for (q = 0, w = 0; q < 5; q++)
    w += a[q] / k + (a[q] % k ? 1 : 0);
  cout << w << endl;
}

복잡도

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

문제