[BOJ] 백준 1773 폭죽쇼

[BOJ] 백준 1773 폭죽쇼

이 문제는 n개의 입력들의 최소공약수가 폭죽쇼의 시간c 안에서 몇회 겹치는지 알아내는 문제다. 최소공약수가 a라고 한다면, 폭죽놀이의 시간 / a = answer 이다.
하지만, 최소공약수를 구할때 구하고싶은 인자가 2개를 넘어간다면, 구현하기 매우 까다롭다.
따라서 한 배열(폭죽쇼의 시간만큼의 크기)에서 각 인자들의 배수 인덱스를  1로 덧씌우는 간단한 방법을 채택하여 문제를 풀었다.

소스코드 :

#include 
using namespace std;


int main() {
 int n, t;
 cin >> n >> t;
 cin.ignore();
 
 // 덧씌울 배열 p 동적할당.
 int *p = new int[t+1] {0, };
 for (int i = 0; i < n; i++) {
  int q;
  cin >> q;

  // 매회 <=t 범위의 배수마다 1을 덧씌워줌.
  for (int w = 0; w <= t;) {
   p[w] = 1;
   w += q;
  }
 }
 int cnt = 0;
 for (int i =1 ; i <= t; i++) {

  // 덧씌운 1이 나올경우, cnt ++;
  if (p[i] == 1) {
   cnt++;
  }
 }
 cout << cnt << endl;
 delete[] p;
}