바이러스

ProgrammingAlgorithm
Algorithm, 바이러스

바이러스가 1마리 있다. 이 바이러스의 수는 1초 후에 2배로 불어날 수도 있고 1/3(소숫점 이하 버림)로 줄 수도 있다. 현재 몇 마리의 바이러스가 존재하는지 주어질 때 1마리의 바이러스에서부터 최소 몇 초의 시간이 흘러 현재 상태가 되었는지 구하시오.

ex) 현재 바이러스가 7마리 있다면,
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 21 -> 7
이보다 더 빠른 시간 안에 7마리가 될 수는 없다.
따라서 답은 8초이다.

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
import java.util.*;
public class Virus{
  public static void main(String[] args){
    int num = 7;
    Queue queue = new LinkedList();
    queue.add(new Element(1, 0));
    while(true){
      Element e = queue.remove();
      if(e.getNum() == num){
        System.out.println(e.getTime());
        return;
      }
      queue.add(new Element(e.getNum() * 2, e.getTime() + 1));
      queue.add(new Element(e.getNum() / 3, e.getTime() + 1));
    }
  }
  class Element{
    private int num;
    private int time;
    public Element(int num, int time){
      this.num = num;
      this.time = time;
    }
    public int getNum(){
      return num;
    }
    public int getTime(){
      return time;
    }
  }
}
Share Comments