[백준] 1309번 동물원

문제링크: https://www.acmicpc.net/problem/1309

아이디어

• 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어있게 배치할 수는 없으므로, 대각선으로만 배치 가능 $\rightarrow$ i번째 줄의 특정 칸에 사자를 배치하면, i-1번째 줄에 사자를 배치할 수 있는 위치는 정해져있음 혹은 아예 배치하지 않는 것이 가능
• $f(n) :=$ 세로로 n칸인 우리에 사자를 가두는 경우의 수
• $f(n) = 2+f(n-1)+2\Sigma_{i=0}^{n-2} f(i)$, where $f(0) = 1$ and $f(1) = 3$
  • n번째 칸에만 사자를 배치하는 경우: 2
  • n번째 칸을 비워두는 경우: $f(n-1)$
  • n번째 칸에 사자를 배치하는 경우의 수: $2\Sigma_{i=0}^{n-2}f(i)$

코드

import sys
input = sys.stdin.readline


class Cage():
    def __init__(self, size: int = 1) -> None:
        self.size = size
        self.capture = [0]*(self.size+1)
        self.capture[0] = 1
        self.capture[1] = 3

    def construct_cage(self):
        prev_cases = 0
        for i in range(2, self.size+1):
            prev_cases += self.capture[i-2]
            self.capture[i] = (self.capture[i-1] + 2*(1+prev_cases)) % 9901

    def ways_to_capture(self, idx: int = 1):
        return self.capture[idx]


if __name__ == "__main__":
    lion_cage = Cage(int(input()))
    lion_cage.construct_cage()
    print(lion_cage.ways_to_capture(lion_cage.size))

결과

필요에 의해, 주어진 사이즈 이하로 케이지를 만들 경우에도 가능한 경우의 수를 출력할 수 있도록 함수를 구성하였다.