백준 1773번 폭죽쇼

문제

학생들은 3주가 지난 기념으로 매점에서 1월 1일이 지나 싸게 파는 폭죽을 사서 터뜨리고 있다.

폭죽쇼를 하는 동안 N명의 학생들이 폭죽을 터뜨린다. 그리고 이 N명의 학생은 각각 일정한 주기로 폭죽을 터뜨린다. 물론 이 주기는 학생들마다 같을 수도, 다를 수도 있다. 그리고 우리는 초 단위로 관찰을 하고, 폭죽 역시 초 단위로 터진다.

폭죽쇼가 끝날 때까지 얼마나 많은 시간동안 밤하늘에 폭죽이 터지는 것을 볼 수 있는지 궁금해 하는 조교를 도와주자.

입력

첫 줄에 폭죽을 터뜨리는 학생의 수 N(1 ≤ N ≤ 100)과 폭죽쇼가 끝나는 시간 C(1 ≤ C ≤ 2,000,000)가 주어진다. 그 다음 N개의 줄에는 학생들이 폭죽을 터뜨리는 주기가 한 줄에 하나씩 주어진다. 주기는 1보다 크거나 같고, C보다 작거나 같은 자연수이다.

 

 

백준 풀면서 이해 안되는 점이 같은 알고리즘으로 구현하는 데 틀렸다고 하는 경우가 있다. 런타임에러도 아니고 시간초과도 아니고 답이 틀렸다고 하는데, 구글에서 찾아보면 내 알고리즘과 똑같이 풀었지만 배열 선언이나 벡터를 사용했거나 하는 차이 뿐 구조 자체가 완전히 똑같음...

근데 알고리즘을 바꿔서 풀어보면 맞았다고 하길래 바꿔서 풀었다... 짱나네 아이디어는 C까지의 각 시간에 대한 각 학생들의 주기를 각각 비교해서 자신의 주기에 맞으면 전부 bool값을 참으로 세팅한 뒤에 참인 경우에 대해 한꺼번에 비교해서 카운트를 올리는 방법 . 4,6,12의 주기라면 1초부터 C초 까지 초가 올라가는 가운데에 12초에서 4,6,12는 전부 참이지만 각각 카운트를 올리는 것이 아니라 3중 한명이라도 참인 경우에 참으로 세팅되어 있다가 후에 참이면 카운트를 올림.

 

 

 

#include <iostream>



using namespace std;
int cnt=0;
bool check=false;

int main(void)
{
int N,C;


cin >> N >> C;

   int arr[N];
   
   for(int i=0; i<N; i++)
   {
     cin >> arr[i];
   }
   

 for(int j=1; j<=C; j++)
{ 
  check = false;
   
  for(int i=0; i<N; i++)
{   
     if(j%arr[i] ==0)
     {
      check = true;
     
 }
   }
 if(check)
 {
  cnt++;
 }
 
}
       


 
   cout<<cnt;

}

 

원래 아이디어는 visit배열을 선언해서 각 학생들이 폭죽을 터뜨린 시간을 visit 기록하고 visit가 아니면 기록 하는 식으로 중복을 방지하는 방식이였으나 이는 벡터도 필요없고 최소공배수의 개념도 필요 없다.