본문 바로가기
[C++] 알고리즘 교육/11~13. 자료구조

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

by 안산학생 2019. 4. 24.

문제


철수네 마을에는 갑자기 전염병이 유행하기 시작하였다. 이 전염병은 전염이 매우 강해서, 이웃한 마을끼리는 전염되는 것을 피할 수 없다.
철수네 마을은 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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#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;
}
 

댓글