9465 - 스티커

한 스티커(칸)를 선택하면 인접한 칸은 선택할 수 없게 된다.
그럼 대각선만 남게 되는데, 그 대각선 칸도 위 선택을 반복하게 된다.

A B C D
E F G H

위와 같이 있을 경우, A 를 선택한다면 C D F G H 중에 선택하게 된다. (하지만 대각선을 선택하는게 가장 좋기 때문에 F 가 선택될 것이다.)
여기서 F 를 선택했다고 생각하면 남은건 C D H 인데, C D 중 더 큰 것을 선택한 것이 F 를 선택했을 때의 최선의 선택이다. X번의 최선의 선택을 F(X) 라 하자.
이해하기 쉽게 위아래로 나누자면 윗줄 중에서 최선의 선택을 F(X), 아랫줄은 G(X) 라고 했을 때,
F(X) 는 F.x(윗줄 x번째 스티커의 값) 과 max( G(X+1), G(X+2) )을 더한 값이 최선의 선택일 것이다.

50 10 100 20 40
30 50  70 10 60

은 아래와 같이 진행된다.

(Base case)
0 0 0 0 40
0 0 0 0 60

0 0 0 20+60=80 40
0 0 0 10+40=50 60

(남은 대각선 방향에서 가장 최선의 값을 누적. 같은 줄은 이미 이전에 확인을 함!)
0 0 100+max(50,60) 80 40
0 0 70+max(80,40) 50 60

(사실 여기서부터는 대각선 방향에서 가장 최선을 볼 필요가 없다. 왜냐면 대각선 방향이 이미 최선이 되었기 때문)
0 10+150 160 80 40
0 50+160 150 50 60

50+210 160 160 80 40
30+160 210 150 50 60

이제 F(0) 과 G(0) 중에서 무엇이 더 큰가만 확인하면 된다.