취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24451번 문제인 飴 2 (Candies 2)이다.
문제는 아래 링크를 확인하자.

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

N개의 사탕이 일렬로 놓여있을 때, 어떤 K개의 연속한 사탕을 살펴도 2개를 넘지 않는 사탕만을 골라 고른 사탕의 맛있는 정도의 총합을 최대화시키는 문제이다.

dp[i][j]를 (마지막으로 고른 두 개의 사탕의 인덱스가 i와 j인 경우의 사탕의 맛있는 정도의 총합의 최댓값)으로 정의하자. (단, i < j)

이 때, dp[i][j]는 1 이상 j-K 이하의 정수 k에 대하여 max(dp[k][i]) + arr[j]로 표현할 수 있음을 관찰하자. 단, 1 이상 j-K 이하의 정수가 존재하지 않는다면 dp[i][j]는 arr[i] + arr[j]로 계산하자. 위 식에서 k의 역할은 "i 이전에 먹은 사탕의 위치 후보"이다.

max(dp[k][i])를 매번 직접 계산하는 것은 오래 걸리므로 이 또한 별도의 메모이제이션을 이용해 시간복잡도를 감소시켜주자.

위 점화관계를 이용하는 것으로 문제를 O(N^2)에 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N, K;
ll arr[3001];
ll dp[3001][3001];
ll dpdp[3001][3001];
bool visited[3001][3001];

ll func(int q, int i) {
	if (q <= 0) return 0LL;
	if (visited[q][i]) return dpdp[q][i];
	visited[q][i] = 1;
	return dpdp[q][i] = max(func(q - 1, i), dp[q][i]);
}

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

	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> arr[i];

	ll ans = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = i + 1; j <= N; j++) {
			if (j <= K || i == 1) dp[i][j] = arr[i] + arr[j];
			else dp[i][j] = func(min(j - K, i - 1), i) + arr[j];
			ans = max(ans, dp[i][j]);
		}
	}

	cout << ans;
}