[BOJ/백준] 2240 자두나무

import sys

def input():
    return sys.stdin.readline().rstrip()


N,W = map(int,input().split())


dp = [[0 for _ in range(W+1)] for _ in range(N)]

first = int(input())

if first == 1:
    dp[0][0] = 1
else:
    dp[0][1] = 1


for ind in range(1,N):
    num = int(input())
    num -= 1
    dp[ind][0] = dp[ind-1][0]
    if not num:
        dp[ind][0] += 1
    for j in range(1,W+1):
        dp[ind][j] = max(dp[ind-1][j],dp[ind-1][j-1])
        if j%2 == num:
            dp[ind][j] += 1

print(max(dp[N-1]))

다이나믹 프로그래밍을 이용한 문제였다.

 

 

2차원 배열 dp을 정의했다.

 

dp[N][W] 는 n번째일때의 w 번 이동했을때의 최대값인 경우로 dp 배열을 정의했다.

 

그러면 dp[n][w]일때의 값은 dp[n-1][w-1] 이나 dp[n-1][w]의 최대값이 될것이다. 이동을 했거나, 이동을 하지 않았거나 이다.

 

그리고 짝수번을 움직였을때에는 무조건 1번 나무에 있고, 홀수번을 움직였을때에는 무조건 2번나무에 위치해있는다.

 

이점을 이용해

 

dp[n][w] = max(dp[n-1][w-1],dp[n-1][w])을 비교해주고,

 

현재 떨어진 과일나무의 위치와 움직인 횟수의 홀수짝수가 동일 할 때에는

 

해당 위치에서 현재 떨어지는 열매를 먹을수 있는것이므로, 1개씩 더해주면 된다.

 

dp배열을 정의하고, 움직인 횟수가 홀수 짝수일때를 비교를 해, 1번나무에 위치해있는지,

 

2번나무에 위치해있는지를 구분해주면, 3차원 배열을 쓰지 않고도, 2차원 배열만으로도 풀수 있는 문제였따.