백준 2156: 포도주 시식 (DP / with Swift)

간만에 점화식을 세우기 복잡했던 DP 문제였다.

 

이 문제처럼 3개 연속 취할 수 없는 규칙이 있는 경우, 마지막으로 밟은 곳이 어디인지를 관리해주는 것이 중요하다.

즉, dp[i]가 의미하는 것은 i번째 계단을 밟는 경우에 취할 수 있는 최댓값이 될 것이다.

 

그렇다면, dp[i]를 구할 때 고려해야할 것은, 

1. i-1 계단을 밟았을 경우 => i-1과 i를 밟는 경우이므로, i-2를 밟을 수 없다. 

따라서 쉽게 생각할 수 있는 것이 dp[i-3] + data[i-1]이다.  하지만, dp[i-4] + data[i-1]도 존재한다는 것을 생각해야한다. 

 

i-5  i-4  i-3  i-2  i-1 i  와 같이 할 경우 최대가 될 수 있기 때문

2. i-2 계단을 밟았을 경우 => 더이상 신경 쓸 것이 없다. (i-2를 밟았기 때문에 i-1을 밟을 수 없음)