[BOJ]백준 22114번: 창영이와 점프(C++)/DP

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

22114번: 창영이와 점프

오랜만에 푸는 DP문제 

처음에 bottom-up으로 풀려고 했는데 점화식이 계속 생각이 안 나서 재귀로 푼 다음에 메모이제이션 적용했다

dp도 재귀(top-down)이기 때문에 base case, inductive step, memoization 이 세 가지 위주로 설계해야 할 듯 

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

int n, k, l[100005], dp[2][100005],ans;

int func(bool b, int cur) {
	if (cur == n)return 1;

	int& ret = dp[b][cur];
	if (ret != -1)return ret;

	ret = 1;

	if (l[cur] <= k)
		ret = func(b, cur + 1) + 1;
	else if (!b)
		ret = max(func(true, cur + 1) + 1, ret);

	return ret;
}

int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf("%d", &l[i]);

	fill(&dp[0][0], &dp[1][100001], -1);
	dp[0][n] = dp[1][n] = 1;

	for (int i = 1; i <= n; i++)
		ans = max(ans, func(false, i));

	printf("%d", ans);
	return 0;
}