BOJ 6246 - 풍선 놀이

문제

BOJ 6246 - 풍선 놀이

1번부터 N번까지 번호가 붙은 풍선이 있다. TC개의 규칙이 주어지며, 각 규칙은 시작 번호 S와 간격 T로 이루어진다. 규칙에 따라 S번, S+T번, S+2T번, ... N번 이하의 풍선이 터진다. 모든 규칙을 적용한 뒤 터지지 않은 풍선의 수를 출력한다.

입력

첫 줄에 N과 TC가 주어진다. 이후 TC줄에 걸쳐 S와 T가 주어진다.

출력

터지지 않은 풍선의 수를 출력한다.

예제

풀이

각 규칙에 따라 해당하는 번호의 풍선을 표시하고, 표시되지 않은 풍선의 수를 센다.

1. 크기 N+1의 배열 f를 0으로 초기화한다.
2. TC개의 규칙 (s, t)를 처리하며 j = s에서 시작하여 j += t씩 증가하며 N 이하인 동안 f[j] = 1로 표시한다.
3. 1번부터 N번까지 f[i] == 0인 원소의 수를 세어 출력한다.

핵심 아이디어: 풍선 번호를 인덱스로 하는 배열을 마킹 배열로 사용하여, 터진 풍선을 O(1)에 표시한다. 등차수열 방식으로 각 규칙을 순회하므로 규칙당 최대 N/T번 반복하며, 에라토스테네스의 체와 유사한 구조를 가진다.

코드

#include <iostream>
 
using namespace std;
 
int main()
{
  int f[10001] = {};
  int n, tc;
  int s, t;
  cin >> n >> tc;
  for (int i = 0; i < tc; i++)
  {
    cin >> s >> t;
    for (int j = s; j <= n; j += t)
    {
      if (f[j] == 0)
      {
        f[j] = 1;
      }
    }
  }
  int tot = 0;
  for (int i = 1; i <= n; i++)
  {
    if (f[i] == 0)
    {
      tot++;
    }
  }
  cout << tot;
}

복잡도

• 시간: O(N + TC × N/T) — 각 규칙당 N/T번 반복 (조화급수 합 수준)
• 공간: O(N) — 크기 N+1 마킹 배열