[BOJ_Python] 1309.동물원

문제

https://www.acmicpc.net/problem/1309

 

사용 알고리즘

DP

 

풀이

고려사항

1. 현재 위치에서 상하좌우에 사자가 존재하는지

2. 상하좌우에 사자가 존재하지 않는다면 사자를 놓을 것인지

 

후기

1. 이 문제의 keypoint는 점화식을 찾는 것이다.

우선 한 줄씩 늘려보면

n = 1인 경우 아래와 같은 방법으로 3가지 경우의 수가 존재한다.

n = 2인 경우 

 - 아무것도 없는 경우에 n = 1과 같이 3가지 경우

 - 한 마리가 있는 경우에 사자를 놓지 않거나 반대편에 놓는 경우 

   즉, 2 * 2 = 4가지 경우의 수가 존재하므로

 - 총 7가지 경우의 수가 존재한다.

 

이런 방법으로 점화식을 찾다보면

두 쪽 모두 비어 있는 경우 * 3 + 사자가 한 쪽에 존재하는 경우 * 2의 규칙을 발견할 수 있다.

- 두 쪽 모두 비어 있는 경우는 지금의 두 단계 전의 경우의 수와 같고

   (두 단계 전의 경우의 수에 빈 우리만 붙인 경우)

- 사자가 한 쪽에 존재하는 경우는 한 단계 전의 경우의 수에서 두 단계 전의 경우의 수를 뺀 경우와 같다.

   (한 단계 전에서 빈 우리만 뺀 경우)

때문에 아래와 같은 점화식을 찾을 수 있다.

dp[i] =  dp[i-2] * 3 + ( dp[i-1] - dp[i-2] ) * 2

= dp[i-2] + dp[i-1] * 2

 

코드

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

 

결과