동물원 실버1 (백준, DP)

2023. 1. 30. 17:09코딩 테스트 준비

728x90
반응형
n = int(input())
dp = [0]*100001
dp[0] = 3
dp[1] = 7

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

print(dp[n-1])

 

풀이

 

n = 0 일 때, 사자를 놓지 않는 경우도 하나의 수로 가정한다고 했으므로 경우의 수는 1이 된다.

 

n = 1 일 때

 

위와 같은 방법으로 사자를 둘 수 있다. 즉, 경우의 수는 3이다.

 

 

n = 2 일 때를 생각해보자.

 

사자를 놓지 않는 방법은, n=1 일때 나올 수 있는 경우의 수만큼 둘 수 있다. 즉, 3이 된다.

사자를 왼쪽 혹은 오른쪽에 두는 방법은 총 4가지가 있음을 쉽게 유추할 수 있다.

 

따라서, n=2 일때 경우의 수는 7이다.

 

 

규칙이 보인다.

 

사자가 없는 경우 3가지 수 아무거나 가능하다. 사자가 있는 경우 빈 우리 혹은 반대 방향으로 둘 수 있다.

 

즉, 현재 우리에서 사자가 있는 우리와 없는 우리로 분리한 뒤빈 우리의 수 × 3 + 사자가 있는 우리 × 2 를 하면 되는 것이다.즉, 점화식은 다음과 같다.

 

dp[i] = (dp[i-2]*3 + (dp[i-1]-dp[i-2])*2)

 

위 점화식을 풀어서 정리하면 다음과 같다.

 

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

 

 

https://my-coding-notes.tistory.com/264

 

[🥈1 / 백준 1309 / 파이썬] 동물원

1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 문제 어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다. 이 동물원에는 사자들이 살고 있는데 사자

my-coding-notes.tistory.com

 

728x90
반응형