[백준 1773] 폭죽쇼 (C#, C++) - soo:bak

문제 링크

1773번 - 폭죽쇼

설명

여러 학생이 각자의 주기로 폭죽을 터뜨릴 때, 폭죽이 터지는 순간이 몇 초인지 세는 문제입니다. 같은 초에 여러 폭죽이 터져도 한 번만 셉니다.

접근법

1초부터 C초까지를 나타내는 배열을 준비합니다. 각 학생의 주기에 대해 그 배수가 되는 시간을 모두 표시합니다. 모든 학생을 처리한 뒤 표시된 칸의 개수를 세면 폭죽이 보이는 총 시간이 됩니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var parts = Console.ReadLine()!.Split();
    var n = int.Parse(parts[0]);
    var c = int.Parse(parts[1]);
    var fire = new bool[c + 1];
    for (var i = 0; i < n; i++) {
      var t = int.Parse(Console.ReadLine()!);
      for (var j = t; j <= c; j += t) fire[j] = true;
    }
    var ans = 0;
    for (var i = 1; i <= c; i++) {
      if (fire[i]) ans++;
    }
    Console.WriteLine(ans);
  }
}

C++

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

typedef vector<char> vc;

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

  int n, c; cin >> n >> c;
  vc fire(c + 1, 0);
  for (int i = 0; i < n; i++) {
    int t; cin >> t;
    for (int j = t; j <= c; j += t)
      fire[j] = 1;
  }
  int ans = 0;
  for (int i = 1; i <= c; i++) {
    if (fire[i]) ans++;
  }

  cout << ans << "\n";

  return 0;
}