[백준] 1309번 - 동물원 (파이썬)

 

백준 1309번 동물원 문제 파이썬 풀이

 

1309번: 동물원

 

 

" 💡 문제 해결 아이디어 "

 

n의 값에 따라 달라지는 결과에서 규칙을 찾아 점화식을 만들어 문제를 해결하였다.

 

 

처음 주어지는 그림을 통하여 계산 결과를 유추해볼 수 있다.

 

규칙

n = 1 , ans = 3

n = 2 , ans = 7

n = 3 , ans = 17

n = 4 , ans = 41

...

 

해당 규칙을 보면 이전 값에 따라 다음 값이 결정되는 규칙이 숨어있다.

 

값들을 살펴보면 n == 3 일 때의 값은

(n == 2일 때의 값) * 2 + (n == 1일 때의 값)

으로 구할 수 있다.

 

그 이후의 수들도 마찬가지다.

 

이를 점화식으로 만들면 다음과 같은 점화식을 얻을 수 있다.

 

dp[i] = dp[i-1]*2 + dp[i-2]

 

실버 레벨정도의 dp문제는 점화식을 찾는 연습을 해두면 쉽게 식을 유추하여 해결할 수 있는 것 같다.

 

코테는 정해진 시간이 있기 때문에 평소 감을 익히기 위해 적당한 난이도의 문제들로 연습을 많이 해두면 좋은 것 같다.

 

 

코드

n = int(input())

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

print(dp[n])