[ boj : 23560 ] 약

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

23560번: 약

해설 : (다른 분들 코드 보면 그냥 수학적으로 푸셨던데 전 그렇게 못풀었습니다)

 

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

14677번: 병약한 윤호

뭔가 병약한 윤호랑 비슷한 문제인 것 같은데, 얘는 점심때는 꼭 점심만 먹어야 된다는 조건 때문에 BFS로는 좀 힘들어 보입니다. ㅠㅠ (사실 제가 풀어보려 했는데 못풀었어요! ㅎㅎ)

 

그래서 다이나믹 프로그래밍으로 풀었습니다.

 

dp[l][r] = l 번째와 r 번째까지 약을 먹었을때 최대로 먹을 수 있는 약

 

점심만 따로 잘 구별해줍시다.

재귀 함수를 통해서 top-down 으로 구현해 주면 됩니다!

 

#include<bits/stdc++.h>

using namespace std;

struct info {
	int l, r, day;
};

int arr[100];
int memo[50][50];

void solve();
int f(int l, int r, int day);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
	while (t--)
		solve();
	return 0;
}
void solve()
{
	int n;
	cin >> n;
	for (int i = 0; i < 3 * n; i++)
		arr[i] = i % 3;
	//for (int i = 0; i < 3 * n; i++)
	//	cout << arr[i] << " ";
	memset(memo, -1, sizeof(memo));
	cout << f(0, 3 * n - 1,0);
}
int f(int l, int r, int day)
{
	if (l >= r)return memo[l][r] = 1;
	int& ret = memo[l][r];
	if (ret != -1)return ret;

	ret = 0;
	if (day != 1) {
		if (arr[l] != 1)ret += f(l + 1, r, (day + 1) % 3);
		if (arr[r] != 1)ret += f(l, r - 1, (day + 1) % 3);
	}
	else {
		if (arr[l] == 1)ret += f(l + 1, r, (day + 1) % 3);
		if (arr[r] == 1)ret += f(l, r - 1, (day + 1) % 3);
	}
	return ret;
}