파이썬 알고리즘 203번 | [백준 1309번] 동물원 dp (사자 우리)

203 . 동물원

1) 어떤 전략(알고리즘)으로 해결?

DPDPDPDP

2) 코딩 설명

<내 풀이>

• 리스트에다가 dp 를 다 담아두면 메모리초과 에러, 바로바로 갱신해주는 것으로 하자

import sys

n = int(sys.stdin.readline().rstrip())
#dp = [0 for _ in range(n+1)]
dp = 1  #  사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수
#chk =  [0 for _ in range(n+1)] # 더할 수 4, chk[0]+dp[1]*2, chk[1]+dp[2]*2
chk = 2

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

import sys

n = int(sys.stdin.readline().rstrip())
#dp = [0 for _ in range(n+1)]
dp = 1  #  사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수
#chk =  [0 for _ in range(n+1)] # 더할 수 4, chk[0]+dp[1]*2, chk[1]+dp[2]*2
chk = 2

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

<내 틀렸던 풀이, 문제점>

메모리 초과

-나누기를 안해줬어

import sys

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

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

dp[0] = 1  #  사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수

chk =  [0 for _ in range(n+1)] # 더할 수 4, chk[0]+dp[1]*2, chk[1]+dp[2]*2
chk[0] = 2

for i in range(1,n+1) :
    #print(i, dp, chk)
    dp[i] = dp[i-1] + chk[i-1]
    chk[i] = chk[i-1] + dp[i-1]*2

print(dp[-1])

나누기 해줘도 나네 배열 문젠가봄

import sys

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

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

dp[0] = 1  #  사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수

chk =  [0 for _ in range(n+1)] # 더할 수 4, chk[0]+dp[1]*2, chk[1]+dp[2]*2
chk[0] = 2

for i in range(1,n+1) :
    #print(i, dp, chk)
    dp[i] = dp[i-1] + chk[i-1]
    chk[i] = chk[i-1] + dp[i-1]*2

print(dp[-1]%9901)

<반성 점>

• 배열 너무 커지면 메모리 초과우

<배운 점>