[BOJ] 9465번: Stickers

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

동적계획법으로 풀기 위해 적절한 점화식을 찾아야합니다. 각 열에 대해 변수를 2개를 두면 점화식을 쉽게 떠올릴 수 있는데, D[i][0] : 0~i-1열 전체 + i열 0행만 있다고 할 떄 최댓값, D[i][1] : 0~i-1열 전체 + i열 1행만 있다고 할 때 최댓값으로 둔다면

D[i][0] = max(sticker[i][0] + D[i - 1][1], D[i - 1][0]);

D[i][1] = max(sticker[i][1] + D[i - 1][0], D[i - 1][1]);

가 됩니다. 스티커의 값이 0이상이기 때문에 이렇게 정의할 수 있습니다. 그림을 그려서 생각해보세요.)

https://github.com/encrypted-def/BOJ/blob/master/9465.cpp