백준: 1309 동물원

문제

1309번: 동물원

 

문제 풀이

Figure 1. 추가 된 공간에 사자가 없을 때의 경우

Figure 2. 추가 된 공간에 사자가 왼쪽에 있을 때의 경우

Figure 3. 추가 된 공간에 사자가 오른쪽에 있을 때의 경우

 이 문제는 위의 그림을 이해한다면 쉽게 점화식을 세울 수 있다. 처음에 N이 1일 경우, 사자가 존재하지 않을 경우와 사자가 왼쪽에 존재할 경우, 사자가 오른쪽에 존재할 경우가 각 1개씩이라는 것을 알 수 있다.

 

 N이 2가 되면 추가된 공간에 사자가 없거나, 사자가 왼쪽에 있거나, 사자가 오른쪽에 있을 경우의 수를 찾아야 한다. 새로운 공간에 사자가 없을 경우 같은 라인에 사자가 겹치거나, 모두 없어도 상관 없으므로 사자가 없는 경우, 왼쪽에 있는 경우, 오른쪽에 있는 경우를 모두 더한다.

 이와 달리 사자가 왼쪽이나 오른쪽에 가기 위해서는 N - 1에 사자가 없거나, N - 1의 사자가 다른 라인에 없어야 한다. 이처럼 1 부터 N이 증가함에 따라 새로운 공간에 사자가 없을 때, 왼쪽에 있을 때, 오른쪽에 있을 때를 계산하여 값을 누적해 간다면 N일 경우의 경우의 수를 계산 할 수 있다.

 

코드

from sys import stdin

if __name__ == '__main__':
    NO, LEFT, RIGHT = 0, 1, 2
    n = int(stdin.readline())
    answer = [1, 1, 1]

    for i in range(2, n + 1):
        n_lion = answer[NO] + answer[LEFT] + answer[RIGHT]
        l_lion = answer[NO] + answer[LEFT]
        r_lion = answer[NO] + answer[RIGHT]

        answer[NO], answer[LEFT], answer[RIGHT] \
            = n_lion, l_lion, r_lion

    print(sum(answer) % 9901)