백준 10777 허니버터칩 (c++) : 피너클

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

10777번: 허니버터칩

다이나믹 문제다.

cin >> n;
for (int i = 0; i < n; i++) cin >> first[i];
cin >> m;
for (int i = 0; i < m; i++) cin >> second[i];
sort(second, second + m);

memset(cache, -1, sizeof(cache));

값을 입력받는것으로 시작한다. 이때 m개의 봉지는 정렬해준다.

int solve(int i, int j, int k, int take) {

solve함수다. int i는 현재 n봉지의 위치, int j는 현재 m봉지의 앞부분의 위치, int k 는 현재 m봉지의 뒷부분, int take는 가져갈수 있는지 없는지를 나타낸다. solve함수에서 우리는 두가지 선택을 한다.

가져가거나, 안가져가거나

만약 가져간다면 우리는 n봉지와 m봉지중 하나에서 가져가야한다.

n봉지는 이미 위치가 정해져있지만 m봉지는 우리가 원하는 아무데나 끼워넣을수있다. 그러니 정렬해준거다.

만약 n봉지를 가져간다면 n봉지의 현재 위치의 봉지를 가져가고 m봉지를 가져가면 가져갈수있는 뒤의 것을 가져간다.

만약 가져가지 않는다면 n봉지와 m봉지중 하나에서 안가져가야한다.

n봉지에서는 똑같이 현재 위치의 봉지를 무시하고 지나가지만 m봉지에서는 가져갈수있는 앞의 것을 무시한다.

 

10

12

6

14

7

1

2

8

예제 입력이다. m은 정렬했다. i, j, k의 위치는 색으로 표시했다. 맨 처음 k는 m-1이 아닌 m에 위치해있는다.

맨처음 시작했을 때는 가져갈수있다. n봉지와 m봉지중 하나에서 가져와야한다. m봉지에서 가져간다면

10

12

6

14

7

1

2

8

무조건 맨 뒤에서 가져가는것이 이득이다. 가장 많은 허니버터칩을 얻는것이 목적이니 말이다.

만약 m봉지에서 가져가지 않는것을 선택한다면

10

12

6

14

7

2

8

무조건 앞의 봉지를 무시하는것이 이득이다. n봉지는 무조건 순서대로 진행하면 된다.

	if (i == n && j == k) return 0;

만약 i==n이고 j==k라면, 즉 끝에 도달했다면 0을 리턴한다.

	int &ret = cache[i][j][k][take];
	if (ret != -1) return ret;

만약 값이 저장되어 있다면 그 값을 리턴한다.

	if (i == n) {
		if (take == 1) return ret = max(solve(i, j, k - 1, 0) + second[k-1], solve(i, j + 1, k, 1));
		else return ret = solve(i, j + 1, k, 1);
	}

만약 i == n이라면 n봉지는 끝에 도달했으니 m봉지에서 함수를 실행해야한다.

take == 1, 즉 가져갈수 있다면 가져가거나 안가져갈수있다.

solve(i, j, k - 1, 0) + second[k-1] -> m봉지에서 가져가는 함수다. 가져가는 것이니 뒤에서 가져간다. 

solve(i, j + 1, k, 1) -> m봉지에서 안가져가는 함수다. 안가져가는 것이니 앞에 값을 무시한다.

take == 0이라면 solve(i, j + 1, k, 1)을 리턴한다.

	else if (j == k) {
		if (take == 1) return ret = max(solve(i + 1, j, k, 0) + first[i], solve(i + 1, j, k, 1));
		else return ret = solve(i + 1, j, k, 1);
	}

만약 j == k라면 m봉지는 끝났다는 것이니 n봉지에서 함수를 실행히야한다.

만약 take == 1이라면 가져가거나 안가져갈수있다.

solve(i + 1, j, k, 0) + first[i] -> n봉지에서 가져가는 것이다.

solve(i + 1, j, k, 1) -> n봉지에서 안 가져가는 것이다.

take == 0이라면 solve(i + 1, j, k, 1)을 리턴한다.

	int ans = 0;
	if (take == 1) {
		ans = max(solve(i + 1, j, k, 0) + first[i], solve(i, j, k - 1, 0) + second[k-1]);
	}
	ans = max(ans, solve(i + 1, j, k, 1));
	ans = max(ans, solve(i, j + 1, k, 1));
    
    return ret = ans;

그 다음엔 n봉지와 m봉지 모두 끝에 도달하지 않았다는 뜻이다.

만약 가져갈수 있다면 max(solve(i + 1, j, k, 0) + first[i], solve(i, j, k - 1, 0) + second[k-1])를 해주고

또 max(solve(i + 1, j, k, 1), solve(i, j + 1, k, 1))도 해준다.

그후 ans를 리턴한다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, m;
int first[3001], second[101];
int cache[3001][101][101][2];

int solve(int i, int j, int k, int take) {
	if (i == n && j == k) return 0;

	int &ret = cache[i][j][k][take];
	if (ret != -1) return ret;

	if (i == n) {
		if (take == 1) return ret = max(solve(i, j, k - 1, 0) + second[k-1], solve(i, j + 1, k, 1));
		else return ret = solve(i, j + 1, k, 1);
	}
	else if (j == k) {
		if (take == 1) return ret = max(solve(i + 1, j, k, 0) + first[i], solve(i + 1, j, k, 1));
		else return ret = solve(i + 1, j, k, 1);
	}

	int ans = 0;
	if (take == 1) {
		ans = max(solve(i + 1, j, k, 0) + first[i], solve(i, j, k - 1, 0) + second[k-1]);
	}
	ans = max(ans, solve(i + 1, j, k, 1));
	ans = max(ans, solve(i, j + 1, k, 1));

	return ret = ans;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> first[i];
	cin >> m;
	for (int i = 0; i < m; i++) cin >> second[i];
	sort(second, second + m);

	memset(cache, -1, sizeof(cache));

	cout << solve(0, 0, m, 1) << endl;
}

전체코드다.