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

Python

[Python] 백준 알고리즘 온라인 저지 1309 동물원

1309 동물원

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

1309번: 동물원

이번 문제도 다이내믹 프로그래밍을 이용해 경우의 수를 계산하는 문제로 주의할 점은 사자가 없는 경우도 경우의 수로 계산한다는 점이었다.

 

알고리즘 분류

• 다이내믹 프로그래밍

---

소스코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [0, 3, 7] + [0] * (n - 2)

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

print(dp[n])

---

풀이

점화식을 만들어 어렵지 않게 풀이가 가능했다. 작은 수부터 경우의 수를 계산해보았다.

N	1	2	3
경우의 수	3	7	17

이를 통해 dp[i] = dp[i-2] + (dp[i-2] * 2)의 점화식을 도출할 수 있다.

이 방법은 수들의 규칙을 찾아 풀이하는 방법이다.

이 방법 외에 더 좋다고 생각되는 방법은 i번째 열에 사자가 없는 경우, 왼쪽에 있는 경우, 오른쪽에 있는 경우로 나눠 계산하는 방법이다.

1. i 번째 열에 사자가 없으면 i-1에는 사자가 없거나 왼쪽, 오른쪽 모두에 있을 수 있다.
2. 왼쪽에 있다면 i-1에는 사자가 없거나 오른쪽에만 있어야 한다.
3. 오른쪽에 있다면 i-1에는 사자가 없거나 왼쪽에만 있어야 한다.

위의 내용을 토대로 아래의 점화식이 성립하게 된다.

1. no[i] = (no[i-1] + left[i-1] + right[i-1])
2. left[i] = (no[i-1] + right[i-1])
3. right[i] = (no[i-1] + left[i-1])

소스코드

import sys
input = sys.stdin.readline

n = int(input())
no, left, right = 1, 0, 0

for i in range(n):
    no = (no + left + right) % 9901
    left, right = no - right, no - left

print((no+left+right) % 9901)

위의 코드는 다른 분의 풀이를 참고하여 작성하였다.

---

풀이 결과

1309 풀이 결과