[백준 6246] 풍선 놀이 (C#, C++) - soo:bak

문제 링크

6246번 - 풍선 놀이

설명

지정한 시작 슬롯과 간격으로 풍선을 꽂은 뒤, 비어 있는 슬롯의 개수를 구하는 문제입니다.

접근법

슬롯마다 풍선이 꽂혔는지 기록하는 배열을 준비합니다.

각 규칙마다 시작 슬롯부터 간격만큼 증가시키며 표시하고, 마지막에 표시되지 않은 슬롯을 세면 됩니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var parts = Console.ReadLine()!.Split();
    var n = int.Parse(parts[0]);
    var q = int.Parse(parts[1]);
    var used = new bool[n + 1];

    for (var i = 0; i < q; i++) {
      var rule = Console.ReadLine()!.Split();
      var l = int.Parse(rule[0]);
      var step = int.Parse(rule[1]);
      for (var pos = l; pos <= n; pos += step)
        used[pos] = true;
    }

    var empty = 0;
    for (var i = 1; i <= n; i++) {
      if (!used[i]) empty++;
    }

    Console.WriteLine(empty);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q; cin >> n >> q;
  vector<bool> used(n + 1, false);

  for (int i = 0; i < q; i++) {
    int l, step; cin >> l >> step;
    for (int pos = l; pos <= n; pos += step)
      used[pos] = true;
  }

  int empty = 0;
  for (int i = 1; i <= n; i++) {
    if (!used[i]) empty++;
  }

  cout << empty << "\n";

  return 0;
}