[dp/백준] 1309번: 동물원

-문제:https://www.acmicpc.net/problem/1309

처음에 n=1,2,3,4일 때 값을 3,7,15,38으로 구해서 점화식을 못 구했지만

다시 갯수 세보니 3,7,17,41이어서 f(n)= 2*f(n-1)+f(n-2)의 점화식을 구했다

답을 구한후 9901로 나눠줘야한다

-정답풀이 1:

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

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

-정답풀이 2: 

n=int(input())
dp=[0 for _ in range(100001)]
dp[1]=3
dp[2]=7

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

 

 

이렇게 풀면 indexerror난다. n==1일 때는 dp=[0,0]으로 인덱스가 1까지 밖에 없는데, 네번째줄에 인덱스 2에 7을 넣기 때문에 indexError가 날 수 밖에 없다.

아래처럼 하고 싶다면 dp를 n+1개의 원소만 생성하는 것 대신, dp=[0]*100001로 초기화하고, dp[-1]이 아닌 dp[n]을 출력하면된다.

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

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