백준 1309번 동물원 파이썬 풀이

백준 1309번 문제

풀이

동물원에 사자는 그래서 몇 마리 있는데요? 하고 물어보고 싶다.

 

우리만 놓고 몇 마리인지는 관계없이 생각해야 한다.

 

가로로도 같이 있으면 안되고, 세로로도 같이 있으면 안된다.

n=1일 때, 왼, 오, 비어두기 세 가지가 있다. 왼=0, 오=1, 비어두기=2 라고 생각하고 풀 것이다.

이전 값이 0(왼)이면 다음 값은 0(왼)에 올 수 없다. 1(오)아니면 2(비어두기)만 올 수 있다.

이전 값이 1(오)일 경우에는 0(왼), 2(비어두기)

이전 값이 2(비어두기)라면 0(왼),1(오), 2(비어두기) 가능!

 

1. n을 입력받는다. n은 사자의 마리수가 아니라, 우리의 세로 갯수이다. a에 넣어준다.

a = int(input())

 

b = [[0]*3 for i in range(a+1)]

b에 세로 개수만큼 [0,0,0]을 생성한다.

 

for i in range(3):

  b[1][i] = 1

세로 개수가 1일 때, 왼(0), 오(1), 비어두기(2)로 1개씩 경우가 생기므로 1을 입력해 준다.

2.세로가 2개 이상일 때부터 a개까지 집어넣어 준다.

for i in range(2,a+1):

  b[i][0] = b[i-1][1] + b[i-1][2]%9901

  b[i][1] = b[i-1][0] + b[i-1][2]%9901

  b[i][2] = b[i-1][0] + b[i-1][1] + b[i-1][2]%9901

3. b[i-1][2]는 비어두기 값인데, 메모리가 초과되서 가장 큰 b[i-1][2](비어두기)를 9901나머지 값으로 바꿔준다.

그래도 메모리가 초과난다면, 앞에 값들도 %9901로 해준다.

 

4.

출력을 9901로 출력한다. %를 왜 두번 하냐고 생각할 수도 있지만, 세 번해도 값은 같다.

9901%9901 = 0

(9901%9901)%9901 =0

((9901%9901)%9901)%9901 =0

숫자가 커져서 메모리가 힘들어 하니까 앞에서 %9901을 해준 것이다.

print(sum(b[a])%9901)