[BOJ]백준 2240번: 자두나무(C++)/DP

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

2240번: 자두나무

오늘 깔끔하게 프로그래머스 미로탈출 푸는게 목표였는데.... ^^흠

DP는 항상 어렵다

특히 for문을 잘 쓰는 bottom-up 방식은 생각이 안 난다

그래서 나는 항상 재귀함수를 구현한 뒤에 메모이제이션을 적용한다

DP는 어렵다 . . .

#include <cstdio>
#include <algorithm>
using namespace std;

int T, W;
int plum[1005], cache[2][31][1005];

int func(int time, int w, int cur) {
	if ((time > T) || (w > W)) {
		return 0;
	}
	int& ref = cache[cur][w][time];
	if (ref != -1)return ref;

	ref = 0;
	if (cur == plum[time])
		ref = max(func(time + 1, w, cur), func(time + 1, w + 1, !cur)) + 1;
	else {
		ref = func(time + 1, w, cur);
		if (w < W)
			ref = max(ref, func(time + 1, w + 1, !cur) + 1);
	}
	return ref;
}

int main() {
	scanf("%d%d", &T, &W);
	for (int i = 1; i <= T; i++) {
		scanf("%d", &plum[i]);
		if (plum[i] == 2)plum[i] = 0;
	}
	fill(&cache[0][0][0], &cache[1][30][T + 1], -1);

	printf("%d", func(1, 0, 1));
	return 0;
}