백준 2240 자두나무

문제

풀이

3차원 메모이제이션을 이용하여 해결하였다. 처음에 풀었을 때는 틀렸는데 그 이유는 1초일 때 1이라고 생각하고 풀어서였다. ==0초일 때 위치가 1이다.==

그런데 2차원도 된다고 하는데 어떻게 하는지 모르겠어서 찾아봤다.

2차원으로 가능한 이유는 현재 위치를 움직인 횟수로 알 수 있다는 것이었다. 이는 0초에서의 위치가 정해져있기 때문에 가능한 것이겠지…

코드

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int tree[1001];
int cache[1001][31][2]; // t일때 w이하 썼을 때 최댓값
int T,W;
int solve(int t, int w, int p) {
    if(w==W+1)
        return 0;
    if(t>T)
        return 0;
    int &ret=cache[t][w][p];
    if(ret!=-1)
        return ret;
    ret = 0;
    ret = max(ret, solve(t+1, w, p) + (p == tree[t]) );
    ret = max(ret, solve(t+1, w+1, p==1?2:1) + (p==tree[t]));

    return ret;
}
int main() {
    cin>>T>>W;
    for(int i=1; i<=T; ++i) {
        cin>>tree[i];
    }
    tree[0] = -1;
    memset(cache, -1, sizeof(cache));
    cout<<solve(0, 0, 1);
    //std::cout << "Hello, World!" << std::endl;
    return 0;
}

Written by@[jungin]

안녕하세요

GitHub