문제

전형적인 디피 패턴의 문제였다.

문제 링크

문제 접근

  • 시간과 이동 횟수를 기준으로 하여 dp 어레이를 만들어 각 시간마다의 값을 업데이트 해나간다면 빠르게 문제를 해결할 수 있다.
  • 여기서 움직인 횟수가 홀수라는 것은 현재 위치가 2번 자두 나무에 있다는 것을 의미한다. (0과 짝수는 1번)
  • dp[i][j](i번째 시간에 j번 바꾼 경우)의 값은 max(dp[i][j - 1], dp[i][j])가 된다.
  • 만일 j에 따라 확인한 현재 위치가 나무랑 갔다면 dp[i][j] + 1을 하면 된다.
  • 그리고 dp 맨 끝에서 가장 큰 값을 찾으면 된다.

코드

#include <cstdio>
#include <algorithm>
using namespace std;
int ans, t, w, n, arr[1001][31];
int main(){
    scanf("%d %d %d", &t, &w, &n);
    if(n == 1)arr[0][0] = 1;
    else arr[0][1] = 1;
    for(int i = 1; i < t; i++){
        scanf("%d", &n);
        arr[i][0] = arr[i - 1][0];
        if(n == 1)arr[i][0]++;
        for(int j = 1; j <= w; j++){
            arr[i][j] = max(arr[i - 1][j], arr[i - 1][j - 1]);
            if(j % 2 == n - 1)arr[i][j]++;
        }
    }
    for(int i = 0; i <= w; i++){
        if(ans < arr[t - 1][i])ans = arr[t - 1][i];
    }
    printf("%d", ans);
}

느낀점

  • 디피!!?!?!