백준 2240번. 자두나무 (Java)

문제 링크 : https://www.acmicpc.net/problem/2240

자두가 먹을 수 있는 자두의 최대 갯수를 구하는 문제입니다.

[현재 시간][자두가 이동한 횟수] 를 배열로 한 DP로 해결을 할 수 있습니다.

위치에 대한 인덱스를 만들지 않은 이유는 자두가 이동한 횟수로 현재 위치를 알 수 있기 때문입니다.

자두는 무조건 나무 1에서 시작합니다.

자두가 0, 2, 4, ... 처럼 짝수번 움직이면 자두의 현재 위치는 나무 1입니다.

만약 자두가 1, 3, 5 .. 처럼 홀수번 움직인다면 자두의 현재 위치는 나무 2입니다.

그렇기 때문에 dp[i][j] 는 나무 1일때와 2일때 서로 겹치는 일이 없습니다.

한가지 주의할 점은 현재 시간이 1일때는 항상 나무 1에 떨어지는 경우만 카운트해야 한다는 점입니다.

그 외에는 자두가 가만히 있는 경우 dp[i-1][j] 와 움직인 경우 dp[i-1][j-1] 로 나누어 처리를 해주면 됩니다.