9465
BOJ 9465 스티커
boj 9465 스티커 위 그림과 같이, 문제의 조건에 따라 변을 공유하는 스티커는 뗄 수 없고, 대각으로만 이동하며 뗄 수 있다. 이 때, 대각으로 이동할 수 있는 경우는 아래 그림과 2가지가 있다. 3칸부터는 이동하면 중간에 거쳐갈 수 있는 칸이 무조건 있으므로 가장 높은 점수를 구하는 문제 조건에 어긋나므로 제외한다. 맨 위 그림을 보면, 스티커를 떼는 경로는 마지막에 떼지는 스티커가 첫번째 줄이냐 두번째 줄이냐로 나눠진다. 테이블 D[i][j]는 j번째 줄의 i번째 칸까지 스티커 점수의 최댓값으로 정의하고, score는 스티커의 점수를 담는 배열이다. 그러면 위의 내용을 점화식으로 정의해보자. D[i][0] = max(D[i-1][1], D[i-2][1]) + score[i][0] D[i][1] ..