[백준 2240] 자두나무 C++

문제

백준 2240 자두나무 C++

2240번: 자두나무

풀이

전형적인 dp문제이다.

1번에서 시작한다는 문구를 놓쳐서 디버깅하는데 시간이 쪼오끔 걸렸다... (2번에서도 시작할 수 있는줄 알았음)

움직이지 않는 경우에는 첫번째에 있는 경우이므로, 그 전칸에서 바로 가져오고

1번째 칸은 1번째에서 그대로 내려오거나 / 2번째 칸에서 바꾸거나

2번째 칸은 2번째에서 그대로 내려오거나 / 1번째 칸에서 바꾸거나 각각 2가지 경우가 있으므로

이를 비교하여 더 큰 값을 취하고 dp배열에 저장해두면 된다.

소스 코드

#include<iostream>
#include<algorithm>
using namespace std;
 
// T, 움직인 횟수, 위치
int dp[1001][31][3];
int num[1001];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int T, W;
    cin >> T >> W;
 
    for (int i = 1; i <= T; i++)
    {
        cin >> num[i];
    }
 
    // 1번에서 시작
    dp[1][0][1] = (num[1] == 1);
    // 2번에서 시작
    dp[1][1][2] = (num[1] == 2);
 
    for (int i = 2; i <= T; i++)
    {
        for (int j = 0; j <= W; j++)
        {
            // 움직이지 않는 경우
            if (j == 0)
            {
                dp[i][j][1] = dp[i - 1][j][1] + (num[i] == 1);
            }
            else
            {
                // 1의 최대 : 1에서 움직이기 X, 2에서 움직이기
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][2]) + (num[i] == 1);
                // 2의 최대 : 2에서 움직이기 X, 1에서 움직이기
                dp[i][j][2] = max(dp[i - 1][j][2], dp[i - 1][j - 1][1]) + (num[i] == 2);
            }
        }
    }
 
    int result = 0;
 
    for (int i = 0; i <= W; i++)
    {
        result = max(result ,max(dp[T][i][1], dp[T][i][2]));
    }
 
    cout << result;
 
    return 0;
}