문제
철수네 마을에는 갑자기 전염병이 유행하기 시작하였다. 이 전염병은 전염이 매우 강해서, 이웃한 마을끼리는 전염되는 것을 피할 수 없다.
철수네 마을은 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
이 문제는 queue 를 사용해서 푸는 문제이다. 내가 queue를 이용해서 해결한 방식은 이러하다.
1. 맨처음에 전염병이 돌기 시작한 마을번호를 queue의 처음에 push한다.
2. 이제 pop을 하는데 pop 하는 마을에서 시작해서 전염병을 옮기는 마을번호들을 queue에 push 한다. 즉 위의 문제를 예시로 처음에 시작하는 마을 3을 push하고 pop할때 3*2 = 6번 마을을 push하고, 3/3 = 1 이므로 1을 push한다 그러면 현재 큐의 상태는 0 6 1 0 0 ... 이다.
3. 이렇게 해서 계속 pop을 하면서 큐가 비어있을 때, 즉 front와 rear가 같을 때 까지 pop과 push를 하고, pop한 횟수를 카운트해서 전체 마을개수 N에서 빼면 정답이 나온다.
4. 주의할 점은 전염병이 번지는 i * 2 와 i / 3 가 전에 나왔던 마을과 겹치면 안된다. 입력이 100,000 이기 때문에 여기서 시간을 줄일 방법을 생각했는데, 나는 arr배열을 따로 선언해서 마을의 번호가 나올때마다 마을 번호에 해당하는 arr 배열에 인덱스를 1 더해 마을을 push할때 arr배열을 검사하여 0이면 push하게 했다.
