[백준] 2240 자두나무

[백준] 2240 자두나무

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

• 메모이제이션 사용

• jadu: 같은 나무에서 연속적으로 떨어지는 자두의 수를 저장하는 벡터

  • jadu[짝수]: 1번 나무에서 연속적으로 떨어진 자두의 수
  • jadu[홀수]: 2번 나무에서 연속적으로 떨어진 자두의 수

input:
7 2
2
1
1
2
2
1
1

jadu:
0 1 2 2 2 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int t, w;
//jadu[짝수]: 1번 나무에서 연속적으로 떨어진 자두의 수
//jadu[홀수]: 2번 나무에서 연속적으로 떨어진 자두의 수
vector<int> jadu;

int cache[1001][31];

//먹을 수 있는 자두의 최대 개수 출력
int solve(int idx, int curW) {
	if (idx >= jadu.size()) return 0;

	//jadu[idx]를 먹은 후 위치를 바꿀지 말지 결정
	int& res = cache[idx][curW];
	if (res != -1) return res;
	
	//위치 바꾸지 않는 경우
	res = max(res, jadu[idx] + solve(idx + 2, curW));

	//위치 바꾸는 경우
	if (curW < w) {
		res = max(res, jadu[idx] + solve(idx + 1, curW+1));
	}

	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> t >> w;

	int curTree;
	cin >> curTree;
	//같은 나무에서 연속적으로 떨어지는 자두의 수
	int cnt = 1;

	//자두 1번 자두나무 아래에서 시작
	if (curTree == 2) {
		//1번 나무 아래 0개의 자두 연속적으로 떨어짐 표시
		jadu.push_back(0);
	}

	for (int i = 1; i < t; ++i) {
		int tree;
		cin >> tree;

		if (tree == curTree) {
			cnt++;
		}
		else {
			jadu.push_back(cnt);
			curTree = tree;
			cnt = 1;
		}
	}
	jadu.push_back(cnt);

	//캐시 초기화
	for (int i = 0; i < 1001; ++i) {
		for (int j = 0; j < 31; ++j) {
			cache[i][j] = -1;
		}
	}

	cout << solve(0, 0);
	
	return 0;
}