BOJ(동물원)(1309)

작성일 | In

정수삼각형 1909번

  • 동물원

  • 가로로 두칸, 세로로 N칸인 아래와 같은 우리 존재
  • 사자를 우리에 가둘 떄, 가로로도 세로로도 붙어 있을 수 없다.
  • 2*N 배열에 사자를 배치하는 경우의 수를 알아내는 프로그램 작성

  • 사자를 한 마리도 배치하지 않는 경우도 하나의 수로 친다

  • 가로의 가능한 방법 -> 0: XX /1: XO / 2: OX /3: OO
  • 그런데 OO인 경우는 불가능하므로 삭제 가능
  • N번째 칸이 0일 떄,
  • N-1번 칸에 올 수 있는 것은, 0,1,2번 다 올 수 있다.
  • N칸이 1일 때 , N-1칸에 올 수 있는 것은 0번, 2번
  • N칸이 2일 때, N-1칸에 올 수 있는 것은 0번,1번

점화식

  • d[n][0] = d[n-1][0] + d[n-1][1] + d[n-1][2]
  • d[n][1] = d[n-1][0] + d[n-1][2]
  • d[n][2] = d[n-1][0] + d[n-1][1]
N = int(input())
d = [[1, 0, 0]]+[[0, 0, 0]for _ in range(N)]
for i in range(1, N+1):
    d[i][0] = d[i-1][0] + d[i-1][1] + d[i-1][2]
    d[i][1] = d[i-1][0] + d[i-1][2]
    d[i][2] = d[i-1][0] + d[i-1][1]
    for j in range(3):
        d[i][j] = d[i][j] % 9901
print((d[N][0] + d[N][1] + d[N][2]) % 9901)

참고자료 codeplus

0%