9465 스티커

스티커가 2줄로 배치되어 있고 각 자리마다 가중치가 주어진다.
한 위치의 스티커를 때어내면, 그 상 하 좌 우의 스티커도 같이 떨어진다고 할 때,
때어낸 스티커의 가중치의 합의 최대를 구하는 문제이다.

전형적인 DP 문제로, 이런 DP를 구상할 수 있다.
바로 이전 스티커가 때어졌다면, 현재 위치의 스티커는 때어낼 수 없다. 하지만, 바로 이전 스티커의 반대편 스티커가 때어졌다면, 그 스티커와 현재위치의 스티커 모두 때어낼 수 있다.
따라서 바로 이전 스티커와 바로 이전 스티커의 반대편 스티커 + 현재 위치의 스티커중의 최대값을 고르면서 DP를 진행하면 정답을 구할 수 있다.

소스