[백준_python] 동물원 1309 DP(Topdown,Bottomup)

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

1309번: 동물원

문제

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

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

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

입력

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

출력

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

문제 해결

n이 10만이 주어짐에서 시간 복잡도 상 dp를 생각해 볼 수 있다.

*다이내믹 프로그래밍 문제 해결을 위한 순서도( https://young1403.tistory.com/35)

1. DP의 정의. D(i)가 무엇이 될지를 정의하기.

2. 점화식 세우기 

3.초기값(초기 설정) 

 

dp문제는 문제에 적힌 '텍스트'를  함수로 정의 내리는 능력을 길러야 한다.  문제에서 점화식을 세우기에 참고할 만한 조건들을 뽑아보면

1. 상하좌우에 인접해있어서는 안 되고

2. 사자를 배치하지 않는 것도 하나의 경우의 수로 계산한다 했다.

 

열은 2로 고정된 행이 증가하는 모양을 띄고 있고이럴 땐  시작점에 제한을 줌으로써 경우의 수를 나눌 수 있음을 생각할 수 있다.

모든 dp문제는 top-down, bottom-up의 방식으로 문제를 해결할 수 있지만 문제에 따라서 문제가 의도하는 바와 조금 더 일치한 방법 혹은 먼저 떠오른 방법을 보통 쓰는 것 같다. 2 방법 모두 쓰려고 노력하지만 되도록이면 바텀업으로 푸려고 하는 것 같다.

 

 

[1] Top-down

TOP-DOWN

n이 0일 때는 사자를 한 마리도 배치하지 않은 '경우의 수'

n이 1일 때는 사자를 왼쪽

n이 2일 때는 사자를 오른쪽에 배치한 경우로 나누어 위의 그림처럼 생각할 수 있다.

 

 

시작점이 세 가지로 쪼개 지기 때문에 3가지 경우로 나누어 생각하여야 하며 점화식은 아래와 같이 정의 내릴 수 있다.

1. dp정의 내리기 :   // D(n, k) : k상태의 n번째 줄에 배치한 경우의 수//

2. 점화식 정의하기

D(n,0) = D(n-1,0) + D(n-1,1) + D(n-1,2). -> 시작점에 배치하지 않은 경우 n-1행엔 모든 

D(n,1) = D(n-1,0) + D(n-1,2)    -> 시작점에 왼쪽에 배치했을 때의 경우의 수

D(n,2) = D(n-1,0) + D(n-1,1)    -> 시작점에 오른쪽에 배치했을 때의 경우의 수

 

3. 초기 설정(불변 값)

n==1일 때 3가지로 쪼갤 수 있고 각 경우에 1가지 경우로 계산 가능하다.

-----------------------------------------------------------------------------------------------

2. Bottom up

위와 같은 생각을 가지고 

dp [i][0] = 어디든 상관없어

dp [i][1] = 이전행의 인접하지 않은 부분, 오른쪽 값

dp [i][2] = 이전행의 인접하지 않은 부분, 왼쪽 값

을 바탕으로 2번째행부터 n번째 행까지 dp배열을 만들 수 있다.

-----------------------------------------------------------------------------------------------

#topdown
import sys
sys.setrecursionlimit(10**6)
n = int(input())
dp = [[0]*3 for _ in range(n+1)]

def D(n,k):
    if n==1:
        return 1
    elif dp[n][k]!=0:
        return (dp[n][k])%9901
    if k==1:
        dp[n][k] = (D(n-1,2) + D(n-1,0))%9901
    elif k==2:
        dp[n][k] = (D(n-1,1) + D(n-1,0))%9901
    elif k==0 :#k==0
        dp[n][k] = (D(n-1,2) + D(n-1,1) + D(n-1,0))%9901
    return dp[n][k] ##

ans = 0
for i in range(3):
    ans += D(n,i) #[n]행의 k : 0,1,2에 대한 합들
print(ans%9901)

#Bottom-up
n = int(input())
dp = [[0]*3 for _ in range(n)]
dp[0][1], dp[0][0],dp[0][2] = 1,1,1

for i in range(1,n):
    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-1])%9901)