[Codeforces] 448C: Painting Fence

예제들을 그림판으로 그려보았다.

 

이 문제는 분할 정복 알고리즘으로 접근할 수 있다.

 

만약 가로로 칠하는 게 있다면, 그 stroke는 제일 밑에 있어야만 한다. 

결국, 제일 작은 높이까지는 가로로 다 칠해줘야 한다. 

 

 

가로가 없는 경우 -> 세로만 있는 경우니깐 답은 n

가로가 있는 경우 -> 최대한 칠할 수 있을 때까지 다 가로로 칠해준다. 남은 부분은 또 다음과 같이 나눌 수 있다.

결국 divide and conquer문제!!

= 재귀로 풀 수 있다.

 

C++ 풀이

 

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

int n;
int a[5001];

int solve(int x[], int size) {
    int i, min_num, ans, p, q;
    min_num = 1000000000;
    for (i = 0; i < size; i++) {
        min_num = min(min_num, x[i]);
    }
    for (i = 0; i < size; i++) {
        x[i] -= min_num;
    }
    ans = min_num;

    // p부터 q까지가 0이 아닌 것들. p앞은 0이거나 없거나. q다음은 0이거나 없거나
    p = 0;
    while(p < size) {
        while(p < size && x[p] == 0) p++;
        if (p == size) break;
        q = p;
        while (q+1 < size and x[q+1] > 0) q++;
        ans += solve(x+p, q-p+1);
    }

    return min(size, ans);
}

int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    cout << solve(a, n);

    return 0;
}