[BOJ] 2240. 자두나무 (🥇, DP)

풀이

자두나무가 2개 있을 때 최대 W까지 둘 사이를 오고가면서 얼마나 많은 자두를 얻을 수 있는지를 구해야 한다.

문제의 예제를 보고 직관적으로 구해보면 처음에는 1번 자두나무 위치에 그대로 서 있는다. 비록 2번 자두나무에서 떨어지긴 하지만 그 뒤의 2,3번 째 자두가 1번에서 떨어지기 때문이다. 그리고 나서 2번 자두나무로 위치를 한 번 옮긴다. 이제 2번 자두나무의 자두 2개를 받는다. 그리고 다시 1번 자두나무로 위치를 옮긴다. 이제 자두를 최대 6개 얻을 수 있다.

몇 번째에 위치를 바꾸느냐에 따라 얻을 수 있는 자두의 개수는 달라질 수 있다. 만일 한 번도 바꾸지 않고 계속 1번 자두나무의 위치에 있다면(시작은 1번 자두나무이다) 최대 얻을 수 있는 자두의 개수는 4개일 것이다. 만약 처음 떨어지는 자두를 받기 위해 시작하자마자 바로 2번 자두나무로 위치를 바꿨다가 다시 2,3번 자두를 얻기 위해 1번으로 돌아오게 되면 최대 방향을 바꿀 수 있는 값을 다 채웠기 때문에 더 이상 위치는 변경할 수 없고 최대 자두는 5개가 된다.

결국 언제 방향을 바꿀 것인가가 중요

만약 위치를 딱 한 번만 바꾼다고 가정해보자. 4번째 자두를 받기 위해서 2번으로 위치를 옮기게 된다. 이때까지 얻은 자두는 1번 자두 2개이다. 위치를 바꾸기 전까지는 단 한 번도 위치를 변경한 적이 없는 상태다. 여기서 위치를 바꾸게 되면 이제 위치 변경 횟수가 1로 증가한다.

왼쪽의 행 번호는 위치를 변경한 횟수, 열 번호는 몇 번째 자두가 떨어지는가를 나타낸다. 3번째까지는 위치를 한 번도 변경하지 않았으므로 0행에 있고, 4번째 자두를 받기 위해 1번 위치를 변경하므로 1행으로 옮기게 된다. 배열의 값으로 나타내면 아래와 같다

arr[1][4] = arr[0][3] + 1

이때 그림에서처럼 자두를 얻는다면 1이 추가되지만 얻지 못한다면 아무것도 추가되지 않는다.

이제 다시 1번 자두나무의 자두를 얻기 위해 6번째에 위치를 다시 변경한다고 해보자. 2번 위치를 변경하기 때문에 2행으로 옮겨지게 되고, 6번째 행으로 가게 된다. 위의 식을 그대로 가져와서 대입하면 아래와 같다.

arr[2][6] = arr[1][5] + 1

7번째 자두 역시 1번 위치에서 떨어지므로 최대 구할 수 있는 자두 6개는 마지막 열에서 얻을 수 있게 된다.

i를 떨어지는 자두의 번호, j를 바꾼 위치의 횟수로 했을 때 dp로 나타내면 다음과 같아질 수 있다.

위치를 변경하지 않았을 때 : dp[i][j] = dp[i][j-1]
위치를 변경했을 때 : dp[i][j] = dp[i-1][j-1]

각 위치에서 자두를 얻을 수 있다면 1을 더한다.

# 자두나무

T, W = map(int, input().split())
nums = [int(input()) for _ in range(T)]

rem = 1
dp = [[0]*(T+1) for _ in range(W+1)]
for i in range(1, T+1):
    if nums[i-1]%2 == rem:
        dp[0][i] = dp[0][i-1]+1
    else:
        dp[0][i] = dp[0][i-1]

for i in range(1, W+1):
    rem = (rem+1)%2
    for j in range(i, T+1):
        dp[i][j] = max(dp[i][j-1], dp[i-1][j-1])
        if nums[j-1]%2 == rem:
            dp[i][j] += 1

print(max(list(map(list, zip(*dp)))[-1]))