(JAVA) 백준 1309번 : 동물원--- [DP]

www.acmicpc.net/problem/1309

1309번: 동물원

 

안녕하세요.

 

해당 문제는 DP(동적 프로그래밍) 관련 문제입니다.

 

문제 해결법은 간단합니다.

 

 

 

 

==========================
ㅇㅁ   ㅁㅇ   ㅇㅁ   ㅁㅇ   ㅁㅁ   ㅁㅁ
ㅁㅇ   ㅇㅁ   ㅁㅁ   ㅁㅁ   ㅁㅁ   ㅁㅁ
ㅇㅁ   ㅁㅇ   ㅁㅇ   ㅇㅁ   ㅇㅁ   ㅁㅇ

==========================

* ㅇ : 성공    ㅁ: 식대

 

 

위와 같은 경우,

 

i = 3인 경우에도, N번째 줄에는 총 3가지(양쪽 칸에 사자를 넣지 않음, 왼쪽칸에만 사자를 넣음, 오른쪽칸에만 사자를 넣음) 존재힙니디.

점화식 도출
1) 양쪽 : dp[k][0] = dp[k-1][0] + dp[k-1][3] + dp[k-1][2]
-> 양쪽 칸에 사자를 넣지 않으면, 이전 칸에서 1)양쪽 2)왼쪽 3)오른쪽 전부 경우의 수를 더할 수 있다.
2) 왼쪽 : dp[k][1] = dp[k-1][0] + dp[k-1][2]
-> 왼쪽 칸에 사자를 넣지 않으면, 이전 칸에서 1)양쪽 2)오른쪽 경우의 수
3) 오른쪽 : dp[k][2] = dp[k-1][0] + dp[k-1][1]
-> 오른쪽 칸에 사자를 넣지 않으면, 이전 칸에서 1)양쪽 2)왼쪽 경우의 수

 

 

 

여기서 끝이 아닙니다.

 

이는 dp[k-1][0] = lionCnt[k-2] 과 같습니다.
그이유는, 아무데도 놓지 않은거라면 그이전까지 놓은 경우의수와 같기때문입니다.
또한, 왼쪽에 놓는 경우와 오른쪽에 놓는 경우의 개수는 같습니다.

 

 

이렇게, lionCnt[] 또한 dp(1차원 결과값 배열) 인데요

여기에 모든 상태의 결과값을 저장합니다.

 

 

이상합니다.

 

감사합니다.

 

소스코드

---