[백준 2240번] 자두나무 (C++)

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

2240번: 자두나무

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, W, result;
int arr[1001];
int dp[3][31][1001]; //위치, 움직임, 시간

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> T >> W;
    for(int i=1; i<=T; i++)
    {
        cin >> arr[i];
    }

    //초기값 위치 0
    dp[1][0][1] = (arr[1]==1);
    dp[2][1][1] = (arr[1]==2);

    for(int i=2; i<=T; i++) //시간
    {
        for(int j=0; j<=W; j++) //움직임
        {
            if(j==0)
            {
                dp[1][0][i] = dp[1][0][i-1] + (arr[i]==1); //위치 1 기준
                dp[2][0][i] = dp[2][0][i-1] + (arr[i]==2); //위치 2 기준
            }
            else
            {
                dp[1][j][i] = max(dp[1][j][i-1], dp[2][j-1][i-1]) + (arr[i]==1); //위치 1 기준
                dp[2][j][i] = max(dp[2][j][i-1], dp[1][j-1][i-1]) + (arr[i]==2); //위치 2 기준
            }
            
        }
    }

    for (int i=0; i<=W; i++) result = max(result, max(dp[1][i][T], dp[2][i][T]));

    cout << result;

    return 0;
}

 

풀이에 다소 헷갈림을 가졌던 dp 문제이다.

주어진 위치, 움직임 여부, 시간 진행도에 따라서 dp 식을 갱신해준다.

dp[위치][움직임][시간]

 

문제에서 1번 나무 아래에서 시작한 것을 참고하여 초기값을 설정해준다.

처음에 1번 나무 이므로 1->1 이동이 없고 시간은 지났기에 dp[1][0][1]의 값을 (arr[1]==1)로 넣어준다.

(자두 여부에 따라 1 or 0)

또 2번 나무로 이동하는 경우에는 1->2 이동이 있고 시간은 지났기에 dp[2][1][1]의 값을 (arr[2]==1)로 넣어준다.

(마찬가지로 자두 여부를 따지는데 2번 나무이기에 값이 2인지 체크)

 

그리고 이후 이중 반복문에서 j의 값에 따라 dp식이 달라진다.

j이 0일때는 움직임이 없이 그대로 가는 것이기에 직전 값 (직전 시간의 위치값) + 자두여부에 따라 값을 갱신해준다.

 

j이 1이상일때 부터는 움직임이 존재하는 것이기에 직전 시간 뿐만 아니라, 직전 움직임에 대해서도 체크를 해줘야 한다.

마찬가지로 직전에 움직임 여부 + 직전 위치 + 자두 여부에 따라 값을 갱신해준다.

 

마지막으로 dp내의 최대값을 출력해주면된다.

처음에 j==0에 대해서 고려를 안하고 풀었다가 시간을 꽤 소모하였다.

 

1번 자두나무 -> 1번 나무 (이동 x)
            -> 2번 나무 (이동 o)
            
2번 자두나무 -> 1번 나무 (이동 o)
            -> 2번 나무 (이동 x)
            
max(1->1, 1->2) + 현 위치 자두 여부 
max(2->1, 2->2) + 현 위치 자두 여부

-> 최종 max 출력

j=0의 경우 이동 x
ex) 1 -> 1 -> 1 -> 1 -> 1
직전 위치 + 현 위치 자두 여부만 판별