BOJ 3282 - ROOMS

문제

BOJ 3282 - ROOMS

N개의 방에 G개의 그룹이 순서대로 배치된다. 각 그룹은 M명으로 구성되며, 방에 최대 2명까지 들어갈 수 있다.

배치 규칙:

• 첫 번째 순환: 방이 가득 차지 않았으면 1명 또는 2명씩 배치한다. M이 홀수이면 마지막 1명은 1인실, 나머지는 2인실.
• N번째 방 이후로 다시 첫 번째 방부터 순환한다 (두 번째 순환부터).
• 두 번째 순환부터는 1인실(현재 1명)에 1명씩 추가 배치한다.

각 방의 최종 인원수를 출력한다.

입력

• 첫 번째 줄에 방의 수 N과 그룹의 수 G가 주어진다.
• 다음 G개의 줄에 각 그룹의 인원 M이 주어진다.

출력

N개의 방 각각의 최종 인원수를 한 줄씩 출력한다.

예제

풀이

방 배치를 두 가지 모드(첫 순환, 재순환)로 나누어 시뮬레이션하는 구현 문제이다.

1. N개의 방 배열 arr을 0으로 초기화한다.
2. 각 그룹의 인원 M을 배치한다.
3. chk = false (첫 순환): 방에 M이 짝수면 2명씩, 홀수면 마지막 1명은 1인실로 배치한다. N번째 방에 도달하면 chk = true로 전환하고 인덱스를 0으로 리셋한다.
4. chk = true (재순환): 현재 방이 2인실이면 건너뛰고, 1인실이면 1명 추가하여 2인실로 만든다.
5. 모든 그룹 배치 후 각 방의 인원수를 출력한다.

핵심 아이디어: chk 플래그로 첫 순환과 재순환 모드를 구분한다. 첫 순환에서는 최대한 2인씩 채우고, 재순환에서는 빈자리(1인실)에만 추가 배치하여 방 낭비를 최소화한다.

코드

#include <iostream>
using namespace std;
 
int N, G;
int arr[100];
int idx;
bool chk;
 
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
 
  cin >> N >> G;
  while (G--)
  {
    int M;
    cin >> M;
    while (M)
    {
      if (chk)
      {
        if (arr[idx] == 2)
          idx++;
        else
          arr[idx++]++, M--;
      }
      else
      {
        if (M == 1)
          arr[idx++] = 1, M--;
        else
          arr[idx++] = 2, M -= 2;
 
        if (idx == N)
          chk = 1, idx = 0;
      }
    }
  }
 
  for (int i = 0; i < N; i++)
  {
    cout << arr[i] << '\n';
  }
}

복잡도

• 시간: O(G * M + N) - 전체 인원 G * M에 비례하여 배치, 출력에 N
• 공간: O(N) - N개의 방 배열