[백준 1309번] 파이썬 - 동물원

백준 1309 - 동물원

시간 제한 2초, 메모리 제한 128MB

# 조건

• 어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

• 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다.
• 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.
• 동물원 조련사의 머리가 아프지 않도록 우리가 2N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자.
• 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력

• 첫째 줄에 우리의 크기 N(1<=N<=100,000)이 주어진다.

출력

• 첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

# 접근 방법

• 문제를 읽으면서 dp를 떠올릴 수 있었다.
• 점화식을 도출하기 위한 규칙을 찾기 위해 N을 0부터 늘려보면
  • N = 0인 경우 1
  • 1인 경우 -> 아무 사자도 없는 경우 1개와 우리 당 1마리씩 들어가는 2가지를 더해 3
  • 2인 경우 => 1 + 4 + 2가 된다.
  • 즉, 새로운 우리 한 줄을 추가하게 되면 더해지는 경우의 수는 사자를 놓는 경우와 사자를 놓지 않는 경우로 나눠진다.
• 사자를 놓지 않는 경우는 이전 dp 값과 동일하다.
• 사자를 놓는 경우는 2가지로 나뉘는데
  • 바로 위의 줄이 비어있는 경우
    • 직전 N의 값 ( 바로 위의 줄 ) 이 비어있는 경우의 수 * 2이다.
    • 즉 dp[i -2] * 2의 값과 같다.
  • 바로 위의 줄에 사자가 있는 경우
    • 위의 줄이 생기면서 증가한 경우의 수와 같다.
    • 즉, 2단계 이전의 값은 1단계 이전의 값에서 아무것도 채워지지 않은 경우의 수를 뺀 값이므로
    • dp[i-1] - dp[i-2] 의 값과 같다.
• 위의 점화식을 정리하면
  • dp[i] = dp[i-1] + dp[i-2] * 2 + dp[i-1] - dp[i-2] 이므로
    • dp[i-1] * 2 + dp[i-2]를 도출할 수 있다.
• 또한 문제 조건에 9901의 나머지로 출력해야 하므로 dp값을 구하면서 계속 나눠준다.

import sys  
input = sys.stdin.readline  

N = int(input())  
dp = [0] * (N+1)  

# N = 0은 아무것도 채워지지 않은 경우 1  
# N = 1은 아무것도 채워지지 않은 경우 1 + 각 칸당 한 마리씩 배치 2가지 = 3  
dp[0] = 1  
dp[1] = 3  

# dp 점화식  
# 새로 한 줄이 추가 되었을 때  
# 사자를 놓지 않는 경우 = 직전 dp값과 동일  
# 사자를 놓는 경우  
# 1) 바로 위의 줄이 비어있는 경우 2단계 이전의 값 * 2와 동일  
#           -> 바로 위의 줄이 비어있는 것은 2단계 이전이랑 같은 상황이므로  
#              2단계 이전에서 각 칸에 1마리씩 넣는 경우의 수(2)를 곱해준 것과 같다.  
# 2) 바로 위의 줄에 사자가 있는 경우 1단계 이전 - 2단계 이전의 값과 동일  
#           -> 1단계 이전에 칸을 추가하며 사자를 넣지않은 경우의 수를 빼줘야 하므로  
#              2단계 이전에서 1단계 이전으로 칸 수가 늘며 새로 생긴 경우의 수와 같다.  
# 즉 dp = dp[i-1] + dp[i-2] * 2 + dp[i-1] - dp[i-2] = dp[i-1]*2 + dp[i-2]  

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

print(dp[N])