[solved.ac 실버1] 1309_동물원 (파이썬, DP)

제한 사항

 

문제

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

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력

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

출력

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

예제

---

나의 풀이

DP로 풀 수 있었던 문제이다.

현재 N번째 칸을 확인하고 있다면 N-1번째 칸에서 왼쪽 칸에 사자가 들어있을 때, 오른쪽 칸에 사자가 들어있을 때, 그리고 두 칸 다 사자가 없을 때 이렇게 3가지 경우가 있을 수 있다.

N번째 칸의 왼쪽 칸에 사자가 들어있는 경우를 구하기 위해서는 N-1번째 칸까지 확인했을 때 오른쪽 칸에 사자가 들어있는 경우와 두 칸 다 사자가 없는 경우를 더하면 되고,

오른쪽 칸에 사자가 들어있는 경우를 구하기 위해서는 N-1번째 칸까지 확인했을 때 왼쪽 칸에 사자가 들어있는 경우와 두 칸 다 사자가 없는 경우를 더하면 되고, 

두 칸 다 사자가 들어있지 않은 경우를 구하기 위해서는 N-1번째 칸까지 확인했을 때 왼쪽 칸에 사자가 들어있는 경우, 오른쪽 칸에 사자가 들어있는 경우, 두 칸 다 사자가 들어있지 않은 경우 모두를 더하면 된다.

코드로 나타내면 다음과 같다.

d = [(0, 0, 1)]  # (왼쪽, 오른쪽, 아무것도)
for i in range(1, int(input()) + 1):
    left = (d[i - 1][1] + d[i - 1][2]) % 9901
    right = (d[i - 1][0] + d[i - 1][2]) % 9901
    none = (d[i - 1][0] + d[i - 1][1] + d[i - 1][2]) % 9901
    d.append((left, right, none))
print(sum(d[-1]) % 9901)

튜플로 하나의 칸을 표현했다.

0번째 칸에서는 0, 0, 1로 표현할 수 있는데 0번째 칸은 사자를 넣을 수 없기 때문에 왼쪽에 넣는 경우와 오른쪽에 넣는 경우 모두 0이 되고, 두 칸 다 넣지 않는 경우는 한 가지 경우가 있기 때문에 1로 초기화 된다.

1번째 칸부터 우리가 찾는 과정인데 위에서 설명한 공식이 정확히 들어맞는다.

추가로 문제의 요구 사항에 따라 9901로 나눈 나머지를 취해주고, 주의할 점은 제일 마지막에 경우의 수를 구할 때 튜플의 3개 값을 모두 더하는데 이때 9901보다 큰 수가 나올 수 있으므로 마지막까지 9901로 나눈 나머지를 취하는 것을 주의해야 한다.

채점 결과