9465:스티커

https://www.acmicpc.net/problem/9465

풀이

1. s : n열의 상태

   • [0] [1] [2]
   • X O X
   • X X O

2. d[n][s]

   • 2 x n 에서 얻을 수 있는 최대 점수. n열에서 뜯은 스티커는 s

3. a[i][j]

   • i열 j행에 들어있는 스티커의 점수

4. 결과

   • d[n][0] = max( d[n-1][0] , d[n-1][1] , d[n-1][2] )
   • d[n][1] = max( d[n-1][0] , d[n-1][2] ) + a[n][1]
   • d[n][2] = max( d[n-1][0] , d[n-1][1] ) + a[n][2]

5. 정답

   • max( d[n][0], d[n][1], d[n][2] )

==> 어렵다. 다시 풀어야함