[C/C++] 백준 - 2240번 : 자두나무

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

2240번: 자두나무

문제

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

 

 

메모이제이션을 적용시켜주어야하는 (고려해야하는) 조건이 무엇인지 파악해보면

위치(1번 나무 or 2번 나무)에서 몇 초가 흐른 상태인지, 그 때 남은 움직일 수 있는 기회를 고려해주어야한다.

모두 큰 수가 아니기 때문에 주어진 메모리 내 모두 사용 가능하다.

 

따라서, 위 3가지를 메모이제이션으로 적용시켜주어 동적계획법 풀이로 문제를 해결할 수 있다.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

// 자두는 T초 동안 떨어짐
// 자두는 최대 W번만 움직임
int T, W;
int cache[3][1003][33];
vector<int> pos;

void input() {
	cin >> T >> W;
	pos = vector<int>(T+1, 0);
	for (int i = 1; i <= T; i++) {
		cin >> pos[i];
	}
}

int change(int x) {
	if (x == 1) return 2;
	else return 1;
}

int path(int position, int delta, int rest) {
	if (delta > T) return 0;
	int& ret = cache[position][delta][rest];
	if (ret != -1) return ret;
	
	ret = 0;
	if (position == pos[delta]) {
		ret = path(position, delta + 1, rest)+1;
		if (rest > 0) ret = max(ret, path(change(position), delta + 1, rest - 1));
	}
	else {
		ret = path(position, delta + 1, rest);
		if (rest > 0) ret = max(ret, path(change(position), delta + 1, rest - 1) + 1);
	}

	return ret;
}

int solution() {
	memset(cache, -1, sizeof(cache));
	return path(1, 1, W);
}

int main() {
	fastio;
	input();
	cout << solution() << endl;

	return 0;
}