K보다 큰 n에 대해 n - 1이하의 자연수 k에 대해 dp[k]의 값과 첫 번째 원소부터 k번째 원소 구간합 S[k] 또한 구해놓았다고 가정하겠습니다.
이 조건들을 바탕으로 dp[n] 값을 구해보면 아래와 같이 쓸 수 있습니다.
dp[n] = max(
dp[n - 1], // n번째 소를 선택하지 않았을 때
V[n] + dp[n -2], // n - 1 번째 소를 선택하지 않았을 때
V[n] + V[n - 1] + dp[n - 3], // n - 2 번째 소를 선택하지 않았을 때
V[n] + V[n - 2] + V[n - 3] + dp[n - 4] // n - 3 번째 소를 선택하지 않았을 때
)
*설명*
K = 3이므로 n, n - 1, n - 2, n - 3 번째 소 중 적어도 하나는 선택할 수 없습니다. k번째(n - 3 <= k <= n) 소를 선택하지 않았을 때 나머지를 선택하는 최선의 방법은 k보다 인덱스가 큰 모든 소를 선택하고 k보다 인덱스가 작은 소들을 선택한 결과가 dp[k-1]과 같아지도록 선택하는 것입니다.
위 식은 n이 바뀜에 따라서 모든 원소가 바뀌기 때문에 이미 들어있는 값들은 재사용할 수 없습니다.
여기서 식을 약간 변형해줄 건데, 우변에 S[n]을 빼주고 더해주겠습니다. 이렇게 해주어도 식의 값은 변화가 없습니다. 또 max(a1, a2, ..., an) + x = max(a1 + x, a2 + x, ..., an + x)을 이용하여 -S[n]을 max 안쪽으로 넣어주면 아래와 같이 식이 변형되게 됩니다.
dp[n] = max(
dp[n - 1] - S[n],
V[n] + dp[n -2] - S[n],
V[n] + V[n - 1] + dp[n - 3] - S[n],
V[n] + V[n - 2] + V[n - 3] + dp[n - 4] - S[n]
) + S[n]
= max(
dp[n - 1] - S[n],
dp[n -2] - S[n - 1],
dp[n - 3] - S[n - 2],
dp[n - 4] - S[n - 3]
) + S[n]
이렇게 표현하면 Xn = dp[n - 1] - S[n]으로 두었을 때 dp[n] = max(X[n], X[n - 1], X[n - 2], X[n - 3]) + S[n]으로 매우 간단하게 식으로 표현할 수 있게 되고, 심지어 "BOJ 11003번 : 최솟값 찾기"에서 사용하는 테크닉을 사용하면 max(X[n], X[n - 1], X[n - 2], X[n - 3])의 값도 빠른 시간 내에 구할 수 있게 됩니다. K의 값이 바뀌더라도 비슷하게 점화식을 세울 수 있습니다.
저도 이 문제를 풀면서 정답 점화식을 보고 역으로 유추해본 내용인데, 여러 곳에서 쓰일만한 테크닉인 것 같습니다.
rlfahs3025 1년 전 2
설명을 위해 먼저 K = 3으로 가정해보겠습니다.
K보다 큰 n에 대해 n - 1이하의 자연수 k에 대해 dp[k]의 값과 첫 번째 원소부터 k번째 원소 구간합 S[k] 또한 구해놓았다고 가정하겠습니다.
이 조건들을 바탕으로 dp[n] 값을 구해보면 아래와 같이 쓸 수 있습니다.
dp[n] = max(
dp[n - 1], // n번째 소를 선택하지 않았을 때
V[n] + dp[n -2], // n - 1 번째 소를 선택하지 않았을 때
V[n] + V[n - 1] + dp[n - 3], // n - 2 번째 소를 선택하지 않았을 때
V[n] + V[n - 2] + V[n - 3] + dp[n - 4] // n - 3 번째 소를 선택하지 않았을 때
)
*설명*
K = 3이므로 n, n - 1, n - 2, n - 3 번째 소 중 적어도 하나는 선택할 수 없습니다. k번째(n - 3 <= k <= n) 소를 선택하지 않았을 때 나머지를 선택하는 최선의 방법은 k보다 인덱스가 큰 모든 소를 선택하고 k보다 인덱스가 작은 소들을 선택한 결과가 dp[k-1]과 같아지도록 선택하는 것입니다.
위 식은 n이 바뀜에 따라서 모든 원소가 바뀌기 때문에 이미 들어있는 값들은 재사용할 수 없습니다.
여기서 식을 약간 변형해줄 건데, 우변에 S[n]을 빼주고 더해주겠습니다. 이렇게 해주어도 식의 값은 변화가 없습니다. 또 max(a1, a2, ..., an) + x = max(a1 + x, a2 + x, ..., an + x)을 이용하여 -S[n]을 max 안쪽으로 넣어주면 아래와 같이 식이 변형되게 됩니다.
dp[n] = max(
dp[n - 1] - S[n],
V[n] + dp[n -2] - S[n],
V[n] + V[n - 1] + dp[n - 3] - S[n],
V[n] + V[n - 2] + V[n - 3] + dp[n - 4] - S[n]
) + S[n]
= max(
dp[n - 1] - S[n],
dp[n -2] - S[n - 1],
dp[n - 3] - S[n - 2],
dp[n - 4] - S[n - 3]
) + S[n]
이렇게 표현하면 Xn = dp[n - 1] - S[n]으로 두었을 때 dp[n] = max(X[n], X[n - 1], X[n - 2], X[n - 3]) + S[n]으로 매우 간단하게 식으로 표현할 수 있게 되고, 심지어 "BOJ 11003번 : 최솟값 찾기"에서 사용하는 테크닉을 사용하면 max(X[n], X[n - 1], X[n - 2], X[n - 3])의 값도 빠른 시간 내에 구할 수 있게 됩니다. K의 값이 바뀌더라도 비슷하게 점화식을 세울 수 있습니다.
저도 이 문제를 풀면서 정답 점화식을 보고 역으로 유추해본 내용인데, 여러 곳에서 쓰일만한 테크닉인 것 같습니다.