[BOJ] 백준 2240. 자두나무 (Gold V)

감각 유지 겸 찾아본 문제. 

많은 사람들이 풀었는데, 나는 안풀었길래 한 번 시도해보았다.

문제는 아래와 같다.

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

2240번: 자두나무

---

의식의 흐름 및 해설

매 초마다 자두를 가져가느냐, 안 가져가느냐에 따라 상태가 달라진다. 만약 같은 초에서 현재 움직인 횟수가 같은 경우, 그리고 위치가 같은 경우는 메모이제이션이 가능한 때이므로 dp로 풀 수 있다. 애초에 생긴 거부터가 dp처럼 생겼다.

 

d[t][cnt][now]: 현재 t초, cnt번 이동, now의 위치에 있을 때 가져간 자두의 개수

 

위와 같이 1000*30*2의 공간복잡도 풀이로 해도 충분히 시간 내에 잘 돌아간다. 여기까지는 아주아주 평범한 기초 dp일 뿐이다. 하지만, 위 3차원 배열을 2차원 배열로 풀 수 있는 풀이가 존재한다.

 

잘 생각해보면 시작 전에는 무조건 1번 자두나무에 위치한다. 그리고 자두나무의 위치는 1번 또는 2번과 같이 두 가지 경우만 가능하다. 따라서 홀수 번 이동하면 2번 자두나무, 짝수 번 이동하면 1번 자두나무임이 자명하다. 위와 같이 boolean값으로 비교가 가능하기 때문에 d[t][cnt]와 같이 2차원 배열로 풀 수 있다!

---

코드

#include <bits/stdc++.h>
#define sz(v) (int)v.size()
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int,pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 1003;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
int T,W,a[MAX],d[MAX][32];
int dp(int cur,int cnt){
    if(cnt>W)return -INF;
    if(cur>=T)return 0;
    int&ret=d[cur][cnt];
    if(~ret)return ret;
    ret=dp(cur+1,cnt);
    if(a[cur]!=cnt%2)ret=max(ret,dp(cur+1,cnt)+1);
    else ret=max(ret,dp(cur+1,cnt+1)+1);
    return ret;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin>>T>>W;
    for(int i=0;i<T;i++){
        cin>>a[i];
        a[i]=a[i]%2;
    }
    memset(d,-1,sizeof(d));
    cout<<dp(0,0);
}

---

사실 처음엔 나도 3차원 풀이로 풀었었는데, 난이도 기여를 보고 2차원 배열로 도전해보았다.

2차원 배열로 푸는 풀이가 재밌어서 '기발한' 태그를 붙이고 블로그에 포스팅해보았다 :)