- Today
- Yesterday
- Total
메이쁘
(JAVA) 백준 1309번 : 동물원--- [DP] 본문
안녕하세요.
해당 문제는 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차원 결과값 배열) 인데요
여기에 모든 상태의 결과값을 저장합니다.
이상합니다.
감사합니다.
소스코드
'Algorithm > Baekjoon' 카테고리의 다른 글
(JAVA) 백준 2098번 : 외판원 순회 --- [DP, TSP, 비트마스크] (2) | 2021.07.18 |
---|---|
(JAVA) 백준 2212번 : 센서 --- [그리디] (0) | 2021.03.12 |
(JAVA) 백준 14938번 : 서강그라운드 --- [다익스트라] (0) | 2021.03.02 |
(JAVA) 백준 10610번 : 30 --- [문자열] (1) | 2021.03.02 |
(JAVA) 백준 2917번 : 늑대사냥꾼 --- [BFS, 다익스트라] (0) | 2020.10.23 |