백준 1309 동물원 파이썬

www.acmicpc.net/problem/1309

1309번: 동물원

n = int(input())

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 3

for i in range(2, n + 1):
    dp[i] = (2 * dp[i - 1] + dp[i - 2]) % 9901

print(dp[n])

 

이 문제는 일단 풀긴했는데 정확히 왜그런지 이해하지 못한채로 얼떨결에 규칙을 찾아버렸다

 

우선, 문제에서 동물을 하나도 배치하지 않은 경우도 하나의 경우의 수라 했으니 dp[0] = 1 로 초기화해준다.

 

그리고 n 이 1로 1*2 의 크기를 갖는 경우,

아무것도 배치 하지 않은 경우, 오른쪽에 배치하는 경우, 왼쪽에 배치하는 경우가 있으므로

dp[1] = 3 이다.

 

n 이 2로 2*2 의 크기를 갖는 경우도 한땀한땀 경우의 수를 찾아봤다. 그리 많지 않으니.. 이 경우 7이 나왔다 dp[2] = 7

 

n 이 3으로 3*2 의 크기를 갖는 경우도 한땀한땀 경우의 수를 찾아봤다. 17.

 

문제의 예시에서 n 이 4인 경우는 41이라 했다.

 

그럼 [1, 3, 7, 17, 41] 이 된다.

 

이 값을 보고 어떤 증가 규칙이 있는지 한참 골똘히 생각했다.

 

생각하다보니 2 * dp[n-1] + dp[n-2]  이라는 결론이 나왔다..

 

그냥 그 뿐이다. 아래부터 한땀한땀 직접 경우의 수를 손으로 세고, 그 값들이 어떤 규칙을 가지고 증가하는지만 고민했다. 

 

나 좀 이상한가...? ㅋ 어쨌든 풀었다.