백준 2240. 자두나무 (DP)

https://www.acmicpc.net/problem/2240

2240번: 자두나무

2시간동안 풀었는데, 못풀었다ㅎ 아래 코드를 참고했다. 

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/2240.cpp 

 

1. 특징

1) dp

 

2. 삽질 포인트

1) 나는 dp 테이블을 i번 이동해서 얻을 수 있는 최대 자두수라고 설정했다. 그래서 점화식을 세우기 쉽지 않았다. 

 

3. 구현 포인트

dp 테이블을 d[현재시간][이동횟수][자두의위치] = 받은 자두의 수라고 설정하면 점화식을 세우기 쉽다. 

t와 w를 순회하며, t시간에 떨어진 자두나무의 위치가 1일 때, 2일 때를 각각 구현해주면된다. 

 

1일때 코드는 다음과 같다. 

d[i][j][1] = max(d[i-1][j][1], d[i-1][j-1][2]) + 1; //i는 현재시간, j는 이동횟수, 자두의 위치가 1이고 떨어진 곳도 1이므로 +1
d[i][j][2] = max(d[i-1][j-1][1], d[i-1][j][2]);

 

4. 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int t, w;

int arr[1002];
int d[1002][32][3]; //d[현재시간][이동횟수][자두의위치] = 받은 자두의 수

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

    cin >> t >> w;

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

    for(int i = 1; i <= t; i++)
    {
        d[i][0][1] = d[i-1][0][1] + (arr[i] == 1 ? 1: 0); //이동횟수가0일때(자두의위치=1)
        for(int j = 1; j <= w; j++)
        {
            if(i < j) break; //걸린시간보다 위치변경횟수가 커질 경우 break
            if(arr[i] == 1)
            {
                d[i][j][1] = max(d[i-1][j][1], d[i-1][j-1][2]) + 1;
                d[i][j][2] = max(d[i-1][j-1][1], d[i-1][j][2]);
            }   
            else 
            {
                d[i][j][1] = max(d[i-1][j-1][2], d[i-1][j][1]);
                d[i][j][2] = max(d[i-1][j][2], d[i-1][j-1][1]) + 1;
            }
        }
    }

    int mx = 0;
    for(int i = 0; i <= w; i++)
    {
        mx = max({mx, d[t][i][1], d[t][i][2]});
    }
    cout << mx;


}