[알고연] (4주차-1) 448C. Painting Fence

448C. Painting Fence

Bizon the Champion isn't just attentive, he also is very hardworking.

Bizon the Champion decided to paint his old fence his favorite color, orange. The fence is represented as n vertical planks, put in a row. Adjacent planks have no gap between them. The planks are numbered from the left to the right starting from one, the i-th plank has the width of 1 meter and the height of ai meters.

Bizon the Champion bought a brush in the shop, the brush's width is 1 meter. He can make vertical and horizontal strokes with the brush. During a stroke the brush's full surface must touch the fence at all the time (see the samples for the better understanding). What minimum number of strokes should Bizon the Champion do to fully paint the fence? Note that you are allowed to paint the same area of the fence multiple times.

이번 주차의 테마는 "분할 정복" 이다. 재귀 알고리즘으로 들어서니까 갑자기 난이도가 확 뛰었다. 특히 이 문제는 첫인상이 백준의 플래티넘 V 난이도인 6549번. 히스토그램과 비슷한 느낌이 들어서 더 무섭게 느껴졌다. 교수님의 풀이는 투 포인터를 이용하여 재귀식 접근을 했는데, 꽤 신기하게 느껴졌다.

solve 함수는 startIdx 지점부터 size만큼 울타리를 칠할 때의 답을 의미한다. 울타리 구간: (startIdx, endIdx)

1. mn에는 울타리 구간에서 가장 낮은 높이가 들어간다. 즉, 가로 1번의 브러쉬로 칠할 수 있는 구간의 개수를 구하게 된다. mn을 구하면 모든 울타리 높이를 mn씩 줄여준다.
2. 이제 p와 q를 이용하여 두 포인터로 울타리가 존재하는 구간을 새로 뽑는다. p는 울타리가 존재하는 첫번째 인덱스, q는 울타리가 존재하는 마지막 인덱스를 가리킨다. 
3. ans에 울타리 구간 [p, q]일 때의 답을 더한다. 이 과정을 재귀적으로 반복하면 된다.
4. 만약 ans가 size보다 크면 그냥 각 울타리를 한번씩만 칠하는게 더 적다는 뜻이므로 size를 출력한다.

#include <bits/stdc++.h>
#define MAX 987654321
 
using namespace std;
 
vector<int> vec;
 
int solve(int startIdx, int size) {
    int mn, ans; 
    int endIdx = startIdx + size;
    mn = MAX;
    for (int i = startIdx; i < endIdx; i++) mn = min(mn, vec[i]); 
    for (int i = startIdx; i < endIdx; i++) vec[i] -= mn; 
    ans = mn;
 
    int p = startIdx, q; 
    while (p < endIdx) {
        while (p < endIdx && vec[p] == 0) p++;
        if (p == endIdx) return min(size, ans);
        q = p;
        while (q + 1 < endIdx && vec[q + 1] > 0) q++;
        ans += solve(p, q - p + 1);
    }
    return min(size, ans);
}
 
int main() {
    cin.tie(NULL);	cout.tie(NULL);	std::ios::sync_with_stdio(false);
    int n; cin >> n; vec.resize(n);
    for (int i = 0; i < n; i++) cin >> vec[i];
    
    cout << solve(0, n) << "\n";
 
    return 0;
}