[c++] 백준 #2879 코딩은 예쁘게

< 풀이 >

original 값과 바뀌어야 하는 값의 차이를 계산했을 때 부호가 같은 값들끼리 따로 그룹으로 묶은 후

각 그룹에서 값을 업데이트한다. 이때 조심해야하는 것은 업데이트 횟수는 각 그룹 안에서 차이 값이 가장 큰 값이라고 착각하기 쉽다는 것이다.

input이

5

1 2 3 4 5

0 0 0 0 0

이런 식으로 되어 있으면 1업데이트, 1~5 업데이트, 2~5업데이트, 3~5업데이트, 4~5업데이트, 5업데이트 이렇게 5번이니까 max 취하면 되는 거 아닌가?? 할건데, 만약 input이

5

3 2 1 2 3

0 0 0 0 0

이런 식으로 되어 있으면 1~5을 업데이트 하고 나면

 

2 1 0 1 2

0 0 0 0 0

이런 식이 되어버린다.

 

그러면 이제 1~2번에서 1을 업데이트, 나머지 1에서 업데이트, 4~5에서 업데이트, 5에서 업데이트 이렇게 총 5번을 해주어야 한다.

 

즉, 하나의 그룹 안에서 가장 작은 차이값만큼을 전체 그룹에서 보정해준 후 나머지 그룹에서 분할정복을 해주어야 한다.

 

** 내가 정말 naive하게 생각을 했어서.. 다음의 질문글을 이해하면서 아이디어를 얻었다.

https://www.acmicpc.net/board/view/6482

 

** 이 문제는 COCI 2010/2011 문제라 여기에서 테케와 풀이를 찾을 수 있다.

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

#define N_MAX 1010
int ori[N_MAX];
int N;

int abs(int a){
    if (a>=0) return a;
    else return -a;
}

int solve(int a, int b){
    if (a > b) return 0; // 범위 초과
    int ret = 0;
    if (a == b) {
        ret = abs(ori[a]); // 한자리짜리 구간
        ori[a] = 0;
        return ret;
    }
    int c = a;
    // 각 그룹에서 가장 작은 차이 값의 idx를 찾는다.
    for(int i=a; i<=b; i++){
        if (abs(ori[i]) < abs(ori[c])) c = i;
    }
    // 그 수만큼 업데이트 후 분할정복
    int amount = ori[c];
    for(int i=a; i<=b;i++){
        ori[i] -= amount;
    }
    ret += abs(amount) + solve(a, c-1) + solve(c+1, b);
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N; 
    for(int i=0; i<N; i++) cin >> ori[i];
    for(int i=0; i<N; i++){
        int b; cin >> b;
        ori[i] -= b;
    } 
    
    // separating groups
    vector<ii> groups;
    groups.push_back({-1, -1}); // dummy
    for(int i=1; i<N; i++){
        if (!(ori[i] * ori[i-1] >= 0)){ // i-1까지 그룹이다!!
            int a = groups.back().second + 1;
            int b = i - 1;
            groups.push_back({a, b});
        }
    }
    groups.push_back({groups.back().second + 1, N-1});

    // for each group!
    int ans = 0;
    for(int i=1; i<groups.size();i++){
        ans += solve(groups[i].first, groups[i].second);
    }
    cout << ans << '\n';

    return 0;
}