BOJ 19456 Cocktails

문제

www.acmicpc.net/problem/19456

19456번: Cocktails

길이 $N$의 수열이 주어지고, 할수 있는 연산은

1. $A_i$의 비용으로 i번째 칸을 체크

2. $B$의 비용으로 연속된 $k$개 칸을 모두 체크

3. $C$의 비용으로 임의의 두 칸을 스왑

일 때 모든 수를 체크하기 위한 최소비용을 구해야 한다.

$K<=N<=500$

 

풀이

연산의 순서를 조금 바꿔서 풀기 편한 꼴로 바꾸자.

Observation 1 : 최적해는 Swap -> Range check -> Single Check의 순서, 즉 3->2->1 순서대로 모든 연산을 실행하는 꼴이다.

먼저 Single Check를 할 칸들은 그 전에 Swap, Range check의 과정에서 체크를 할 필요가 없기 때문에 최대한 미루다가 가장 마지막에 체크해줘도 된다. 또한, Swap의 의미는 칸들을 Range check로 이득을 보기 쉽도록 만들어주는 역할이기 때문에 미리 적당히 배열시킨 다음에 한번에 Range Check 해줘도 된다.

 

Observation 2 : Range update는 배열의 끝 부분을 제외하고는 서로 겹치지 않는다.

Range check를 할 칸들을 미리 정해놓았다고 생각하면 문제는 정해진 칸들을 최소 횟수의 길이 K의 덮개로 덮는 문제이니, 그리디하게 배열하면 절대로 겹칠 수 없다. 배열의 끝에서는 겹칠 수 있는데, 이는 덮개가 배열 밖으로 튀어나간다고 생각하면 겹칠 수 없다.

 

이제, 다음과 같이 크게 2가지 방향을 생각해볼 수 있다.

1. Single Check를 할 칸들은 A, Range check를 할 칸들을 B로 정해놓고 시작

2. Range Check를 할 구간들의 갯수와 위치를 정해놓고 시작

 

2번 경우라 생각하고, 이를 만족하도록 A, B를 써보면 B의 개수는 덮개가 덮는 칸들의 수와 같기만 하면 적당히 swap 하여 모든 칸을 체크할 수 있다. 이제 swap의 수를 편하게 구할 수 있는 방법이 있을까?

 

Observation 3 : swap의 수는 (덮개로 덮인 영역에 있는 A의 수) = (덮개로 덮이지 않은 영역에 있는 B의 수)와 같다.

B의 개수가 덮이는 칸들의 수와 같기 때문에, 덮개로 덮인 영역에 있는 A의 수와 덮이지 않은 영역에 있는 B의 수는 같으며, 그것들을 하나씩 묶어서 스왑해주면 덮개가 덮인 영역에는 B만, 아닌 영역에는 A만 위치하도록 만들 수 있다.

 

다음과 같은 dp를 정의한다.

$dp(pos, cnt)=$1~pos 중 아직 매칭이 완벽하게 되지 않은 덮개로 덮이지 않은 영역에 있는 B의 수

pos가 덮개로 덮이지 않을 경우 A를 배정하면 $dp(pos-1, cnt)+A_i$, B를 배정하면 $dp(pos-1, cnt-1)$가 된다.

 

Observation 4 : 덮개로 덮이는 수들 중 A의 개수가 고정되어 있다면, A는 가장 작은 값들부터 하나씩 선택하는게 최적이다.

지금 비용을 내지 않고 range check로 묶을 수 있는 것들이 B이니, A는 최대한 비용이 싼 값들부터 먹는 것이 당연히 이득이다.

 

따라서 pos가 덮개로 덮이며, 그 덮개의 마지막 위치일 경우, 매칭시킬 B의 개수를 모두 순회하며 매칭을 시켜주면 된다.

 

주의할 점은 cnt는 음수가 될 수 있고(오른쪽부터 매칭을 시키기 때문에 덮개가 왼쪽인지, 오른쪽인지에 따라 음수, 양수가 달라진다), 구간 정렬을 i에 대해서만 해 주어야 $O(N^3logN)$을 피할 수 있다.

 

시간 복잡도 : $O(N^3)$

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 500;
const int INF = 1e9;

int N, K, B, C, A[MAXN+10];
int dp[MAXN+10][MAXN*2+10];

int main()
{
	scanf("%d%d%d%d", &N, &K, &B, &C);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]);

	for(int i=-N; i<=N; i++) dp[0][i+N+1]=INF;
	dp[0][N+1]=0;
	for(int i=1; i<=N; i++)
	{
		int t=max(0, i-K);
		vector<int> V;
		for(int j=t+1; j<=i; j++) V.push_back(A[j]);
		V.push_back(0);
		sort(V.begin(), V.end());
		for(int j=1; j<V.size(); j++) V[j]+=V[j-1];

		for(int j=-N; j<=N; j++)
		{
			dp[i][j+N+1]=INF;
			dp[i][j+N+1]=min(dp[i][j+N+1], dp[i-1][j+N+1]+A[i]);
			if(j-1>=-N) dp[i][j+N+1]=min(dp[i][j+N+1], dp[i-1][j-1+N+1]);
			for(int k=0; k<V.size(); k++) if(j+k<=N) dp[i][j+N+1]=min(dp[i][j+N+1], dp[t][j+k+N+1]+V[k]+B+C*k);
		}
	}
	printf("%d\n", dp[N][N+1]);
}