[알고리즘 12.1.3] 큐 - 전염병

문제

---

철수네 마을에는 갑자기 전염병이 유행하기 시작하였다. 이 전염병은 전염이 매우 강해서, 이웃한 마을끼리는 전염되는 것을 피할 수 없다.
철수네 마을은 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>
 
const int MAX = 100000;
struct Queue{
    
    int arr[MAX];
    int capacity;
    int f, rear;
    int numE;
    
    void create(int y){
        capacity = y;
        f = 0;
        rear = 0;
        numE = 0;
    }
    
    void push(int y){
        if(numE>=capacity){
            printf("Queue Overflow\n");
        }else{
            arr[rear++] = y;
            if(rear>=capacity){
                rear=0;
            }
            numE++;
        }
    }
    
    void pop(){
        if(numE<=0){
            printf("Queue underflow\n");
        }else{
            arr[f] = NULL;
            f++;
            if(f>=capacity){
                f = 0;
            }
            numE--;
        }
    }
    
    int front(){
        if(numE<=0){
            return -1;
        }else{
            return arr[f];
        }
    }
    
};
 
int main(){
    
    Queue q;
    
    int n, k;
    scanf("%d %d",&n, &k);
    
    int check[100000] = {0,};
    
    
    q.create(n);
    q.push(k);
    check[k]=1;
    
    //큐에 수가 있는지, 없는지 확인 
    int flag = 0;
    int div = 0;
 
    while(true){
        //만약 큐에 아무것도 있지 않다면... 
        flag = q.front();
        if(flag == -1){
            break;
        }else{
            q.pop();
            if(check[flag*2]==0 && flag*2<=n){
                check[flag*2]=1;
                q.push(flag*2);
            }
            div = flag/3;
            if(check[div]==0){
                check[div]=1;
                q.push(div);
            }
        }
    }
    
    int sum=0;
    
    for(int i=1; i<=100000; i++){
        if(check[i]==1){
            sum++;
        }
    }
    
    int result = n - sum;
    
    printf("%d\n",result);
    
    
    return 0;
}