19. 전염병

문제

---

철수네 마을에는 갑자기 전염병이 유행하기 시작하였다. 이 전염병은 전염이 매우 강해서, 이웃한 마을끼리는 전염되는 것을 피할 수 없다. 철수네 마을은 1번부터 N번까지 번호가 매겨져 있다. 철수네 마을의 구조는 꽤나 복잡한데, i번 마을에서 출발하면 i * 2 번 마을에 갈 수 있고, 또한 i / 3(i를 3으로 나눈 몫) 번째 마을에도 갈 수 있다. 전염병은 사람에 의하여 옮는 것으로 알려져 있다. 따라서 i번 마을에 전염병이 돌게 되면, i * 2 번 마을과 i /3(i를 3으로 나눈 몫) 번 마을 역시 전염병이 돌게 된다. K번 마을이 가장 처음으로 전염병이 돌기 시작했을 때, 전염병이 돌지 않는 마을의 개수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 전체 마을의 개수 N과, 처음으로 전염병이 돌기 시작한 마을 번호 K가 주어진다. ( 1 ≤ N, K ≤ 100,000 )

 

출력

---

전염병이 돌지 않는 마을의 개수를 출력한다.

 

예제 입력

10 3

예제 출력

4

#include <stdio.h>

int main() {
  bool check[100050];
  int myQueue[100050];
  int front=0,rear=0;
  int n,k;
  
  scanf("%d %d",&n,&k);
  
  check[k] = true;
  myQueue[rear++]=k;

  while(front < rear){
    int current = myQueue[front++];
    
    if(current*2 <=n && check[current*2] == false){
      check[current*2] = true;
      myQueue[rear++] = current*2;
    }
    
    if(current/3 >=1 && check[current/3]==false){
      check[current/3] = true;
      myQueue[rear++] = current/3;
    }
  }
  
  int cnt = 0;
  for(int i=1;i<=n;i++){
    if(check[i] == false){
      cnt++;
    }
  }
  
  printf("%d",cnt);
  return 0;
}

https://github.com/kuminkyu/SoloStudy/blob/master/AlgorithmTest/level19/%EC%A0%84%EC%97%BC%EB%B3%91.c%2B%2B