백준 2240번 자두나무 C/C++ 풀이

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

2240번: 자두나무

 

DP 문제이다.

 

DP는 메모이제이션을 위해 어떤 요소들을 저장할지가 가장 중요한데, 해당 문제에서는 3가지를 꼽을 수 있다.

 

현재 나의 위치, 현재 시각, 이동한 횟수

 

이에 따라서 현재 나의 위치와 떨어지는 자두의 위치에 따라 크게 4가지 선택이 가능한데,

 

If(현재 나의 위치에서 자두가 떨어진다면)

{

   1. 현재 위치에서 움직이지 않고 자두를 먹는다

   2. 현재 위치에서 움직이고 다음턴의 반전을 노려본다.

}

else

{

   1. 현재 위치에서 움직이고 자두를 먹지 않고 다음 턴을 노린다.

   2. 현재 위치에서 움직이고 자두를 먹는다.

}

 

2에서 움직일 수 있으려면 이동 횟수가 정해진 횟수를 넘지 않아야 한다.

 

이를 고려해서 코드를 짜면 쉽게 풀 수 있는 문제이다.

 

#include <stdio.h>
#include <memory.h>
#include <algorithm>

using namespace std;

#define MAX 1001

FILE* in = fopen("input.txt", "r");

int t, w;
int arr[MAX];
// 메모이제이션
int cache[2][MAX][31];

//재귀를 통해 구현한 dp
int dp(int now, int time, int mov) {
	// time이 t가 되면 return
	if (time >= t)
		return 0;
    //cache 체크
	if (cache[now][time][mov] != -1)
		return cache[now][time][mov];
    //현재 위치가 자두가 떨어지는 나무라면
	if (now == arr[time])
	{
		int a = 0, b = 0;
		a = dp(now, time + 1, mov) + 1;
        //이동하기 위해서는 이동 횟수가 남아있어야 함
		if(mov < w)
			b = dp(now ^ 1, time + 1, mov + 1);
		return cache[now][time][mov] = max(a, b);
	}
    // 아니라면
	else
	{
		int a = 0, b = 0;
		a = dp(now, time + 1, mov);
        //이동하기 위해서는 이동 횟수가 남아있어야 함
		if (mov < w)
			b = dp(now ^ 1, time + 1, mov + 1) + 1;
		return cache[now][time][mov] = max(a, b);
	}
}

int main() {
	fscanf(in, "%d %d", &t, &w);
	for (int i = 0; i < t; i++)
	{
		fscanf(in, "%d", &arr[i]);
		arr[i]--;
	}
	memset(cache, -1, sizeof(cache));
	printf("%d", dp(0, 0, 0));
}