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

DP를 이용하는 문제입니다. 저는 D[i][j][k] : i초동안 j번 움직여서 얻을 수 있는 자두의 최대 갯수(마지막에 자두는 k번 자두나무 아래에 위치해있음)으로 두었을 때 D[i][j][0], D[i][j][1]을 채워나가는 방식으로 풀이했습니다.

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

D[i][j][1] = max(D[i - 1][j - 1][0], D[i-1][j][1]) + (num[i] == 1); 입니다. 단, j가 짝수일 때에는 D[i][j][0]만 갱신하고 j가 홀수일 떄에는 D[i][j][1]만 갱신해야 합니다.(j가 짝수일 때 2번 나무 밑에 서있을 수 없고 j가 홀수일 때 1번 나무 밑에 서있을 수 없기 때문입니다.)

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