[알고리즘][백준] 1309번 동물원 - 파이썬(python) 풀이

 

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

1309번: 동물원

---

나의 아이디어는 빈칸을 0 왼쪽에만 칠한걸 1 오른쪽에만 칠한걸 2라고 인덱스를 부여해서 2차원으로 풀어보았는데...

import sys

n = int(sys.stdin.readline())

dp = [[0]*3 for _ in range(n+1)]

dp[1] = [1, 1, 1]

if n == 1:

    print(sum(dp[n]))

else:

    for i in range(2, n+1):

        dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2])%9901

        dp[i][1] = (dp[i-1][0] + dp[i-1][2])%9901

        dp[i][2] = (dp[i-1][0] + dp[i-1][1])%9901

    print(sum(dp[n]))

 

백준에 넣으니 틀렸다고 뜬다...

 

위에서 잘못된 것은 sum(dp[n])을 하고도 9901로 나눈 나머지를 출력해줘야한다

이걸 빼먹어서 틀렸던 것!!

import sys

n = int(sys.stdin.readline())

dp = [[0]*3 for _ in range(n+1)]

dp[1] = [1, 1, 1]

if n == 1:
    print(sum(dp[n]))
else:
    for i in range(2, n+1):
        dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2])%9901
        dp[i][1] = (dp[i-1][0] + dp[i-1][2])%9901
        dp[i][2] = (dp[i-1][0] + dp[i-1][1])%9901
    print(sum(dp[n]) %9901)

 

 

다른 분들이 어떻게 풀었나 살펴보니 2차원으로 풀지않고 1차원으로 푸셨다

이렇게 간단한 점화식이 있었다..!!

# sol 1
import sys

n = int(sys.stdin.readline())

dp = [0 for _ in range(n+2)]

dp[1] = 3
dp[2] = 7

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

dp에 n+2를 해야지 n=1일때 out of range가 발생하지 않는다

(n+1이면 dp = [0, 0] 이라 dp[2] = 7에서 out of range 발생)

# # sol 2
import sys

n = int(sys.stdin.readline())

if n == 1:
    print(3)
else:
    dp = [0 for _ in range(n+1)]
    dp[1], dp[2] = 3, 7
    for i in range(3, n+1):
        dp[i] = (2*dp[i-1] + dp[i-2])%9901
    print(dp[n])

out of range 되는 걸 막기 위해 else문에 dp를 넣을수도 있다!! 

 

1309_동물원.py

0.00MB