DP를 이용하여 해결이 가능하다.
한행만 선택이 가능하므로 행마다 따로 선택할 수 있는 최대값을 계산하여 그 값을 이용하여 따로 최대값을 계산해 준다.
하나를 선택하면 다음을 걸러서 선택할 수 있으므로 점화식은 다음과 같다.
dp[i] = Math.max(dp[i - 2] + dp[i], dp[i - 1])
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 1991 트리순회 (0) | 2018.01.13 |
|---|---|
| [백준][DP] 1149 RGB 거리 (0) | 2017.11.15 |
| [백준] 1504 특정한 최단 경로 (0) | 2017.10.25 |
| [백준][DP] 1463 1로 만들기 (0) | 2017.10.25 |
| [백준][세그먼트 트리] 1275 커피숍2 (0) | 2017.10.25 |