BOJ 14393 Whitespace

문제 링크입니다.

문제 요약

길이 $N ( \le 50)$인 음이 아닌 정수열이 주어집니다. 초기 상태가 $[0]$인 수열을 다음의 두 연산만을 이용해 주어진 수열과 같게 만들기 위해 필요한 최소 연산 횟수를 구하세요.

1. 원하는 원소에 1을 더하거나 뺍니다.
2. 원하는 원소를 복사해 바로 오른쪽에 붙여넣습니다. 예를 들어, $[1,2,3]$에서 2번째 원소를 복사하면 $[1,2,2,3]$이 됩니다.

관찰

$-1$ 연산이 가능하다는 점이 거슬립니다. 1번 예제를 통해 살펴봅시다.

$[3, 2, 3]$을 만들어야 합니다. 당장 보이는 방법으로는 먼저 3을 만든 뒤, 복제를 두 번 하고, 가운데 원소에서 1을 빼는 것입니다. 총 6회의 연산이 필요합니다.

다른 방법으로는 먼저 2를 만든 후, 양옆으로 복사하고, 각각에 1을 더하는 것이 있습니다. 마찬가지로 6회의 연산이 필요하네요.

…오…

$-1$을 써서 이득을 볼 수 있는 경우가 그 양 옆 구간 안에 자기보다 큰 원소가 있을 때뿐입니다. 복사를 통해 수를 불리는 건 나중에 해도 되는 작업이니 우리는 양 옆에 자신보다 큰 원소가 바로 붙어있는 경우만 고려합시다.

$[a, b, c] (b < a < c)$를 만들어야 한다고 합시다. c는 나중에 늘리면 되기 때문에 $[b, a, b]$를 만드는 경우를 고려하는 것으로 충분합니다. 아까의 예제 $[3, 2, 3]$과 비슷한 방식으로, 이 경우 $a$를 먼저 만든 뒤 복제하는 것과 $b$를 먼저 만든 뒤 복제하는 것이 각각 $a+2*(b-a)+2$회의 연산을 필요로 함을 알 수 있습니다.

즉 우리는 $-1$ 연산 없이 항상 최적해를 구성할 수 있습니다!

풀이

$+1$ 연산과 복제 연산만 이용했을 때의 최소 연산 횟수를 구합시다.

원소의 크기를 줄일 수 없기 때문에 최소의 원소부터 만들고 필요하면 양옆으로 복제하는 방식으로 해를 구성하는 것이 최적임을 알 수 있습니다.

따라서 배열에서 최솟값을 찾아 해당 값을 기준으로 배열을 두 부분으로 나누어 각각에서의 최솟값을 구해 주면 문제를 해결할 수 있습니다.

분할 정복 시 매번 최솟값을 찾는 방식으로 간단히 구현하면 ${\cal O}(N^2)$에 작동하는 알고리즘을 얻고, 데카르트 트리를 이용하면 이를 ${\cal O}(N)$으로 줄일 수도 있습니다. 어느 쪽이든 $N \le 50$인 제한에서는 매우 넉넉하게 작동합니다.

코드

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

int ans, a[123];

void solve(int l, int mid, int r, int p){
	if(l > r) return;
	ans += a[mid]-p;
	solve(l, min_element(a+l, a+mid)-a, mid-1, a[mid]);
	solve(mid+1, min_element(a+mid+1, a+r+1)-a, r, a[mid]);
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	int n; cin >> n; ans = n-1;
	for(int i = 1; i <= n; i++) cin >> a[i];
	solve(1, min_element(a+1, a+n+1)-a, n, 0);
	cout << ans;
}