아메바 분열

문제

종찬이는 아메바를 분열시키는 취미가 생겼다. 종찬이는 아메바 하나하나가 모두 소중하기 때문에, 새로 생겨난 아메바는 모두 새로운 이름을 지어주기로 하였다. 이번에 분열시키기로 한 아메바는 아래와 같은 특성을 가진다.

• 아메바가 분열하여 두 개체로 완전히 나뉘는 데에는 1분이 걸린다.
• 분열한 아메바 중 하나는 곧바로 분열을 시작하고, 다른 하나는 delay분간 휴식 후 분열을 시작한다.
• 분열하면 기존의 개체는 사라지고 새로운 두 개체가 생긴 것으로 본다.
• 분열되는 도중에는 기존의 개체가 남아있고, 아직 새로운 개체가 생겨나지 않은 것으로 본다.

종찬이는 아메바 한 개체를 분열 시키기 시작한 후, N분 후까지 만들어진 모든 아메바 개체에 새로운 이름을 지어주기로 했다. 종찬이가 준비해야 하는 아메바의 이름은 총 몇 개인가?

입력설명

• 0 <= delay <= 10
• 1 <= N <= 50

출력설명

준비해야 하는 이름의 수를 정수로 출력

매개변수 형식

• delay = 1
• N = 2

반환값 형식

5

예시 입출력 설명

아래와 같이 총 5개의 이름을 지어야 한다.

 

 

문제 풀이 방법

BFS를 사용하였다. Queue에 아메바가 분열을 할 수 있는 시간까지 남은 시간을 넣는다. 즉 0이라면 바로 분열이 가능하고 0이 아니라면 그 시간만큼은 휴식기에 들어간 아메바인 것이다.

0이므로 바로 분열을 하게 되면 2개의 추가적인 이름이 더 필요하다.

 

import java.util.*;

class Solution {
    public int solution(int delay, int N) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        int count = 1;

        for (int i = 1; i <=N ; i++) {
            Queue<Integer> newQueue = new LinkedList<>();

            while(!queue.isEmpty()) {
                int a = queue.remove();

                // 아메바가 바로 분열이 가능한 시간(0) 이라면
                if(a == 0 ) {
                    newQueue.add(0);  // 바로 분열가능한 아메바 1개
                    newQueue.add(delay); // 휴식기에 접어든 아메바 1개
                    count += 2;
                } else {

                    // 1만큼의 시간 휴식을 취했기 때문에 -1을 하고 다시 넣는다.
                    newQueue.add(a-1);
                }
            }
            queue = newQueue;
        }
        return count;
    }
}