[C++] 32999번 Ribbon on the Christmas Present

https://www.acmicpc.net/problem/32999

---

 

25/01/06

 

 

간단한 그리디+구현 문제다.

---

 

문제 접근 방식:

 

 

그니깐, 쉽게 생각하면 덧칠한다고 생각하면 된다.

 

한 번의 붓질로 같은 밝기를 쭉 칠할 수 있는데, 덧칠하면 덧칠할 수록 더 어두워지는 것이다.

 

근데, 붓질 횟수가 최소가 되려면, 한 번 쭉 붓질할 때 최대한 많은 칸을 칠하는 것이 이득일 것이다.

 

예를 들어 $[50, 100, 50, 50, 100, 50]$이라면 맨 처음 $50$칠할 때 처음 칸부터 끝 칸까지 칠하고, 이후 2번째, 5번째 칸에 $50$만큼 더 덧칠하면 3번으로 완성할 수 있다.

 

이걸 코드로 구현해본다면, 기존 주어진 $A$가 있고, 그 배열의 0에 의해 끊어지지 않은 연속된 구간이 있다면 그 구간의 최솟값을 찾고, 그 최솟값을 구간에서 연속해서 쭉 뺀 후, 횟수를 1회 더한다.

 

이걸 $A$가 0배열이 될 때까지 반복하는 형식으로 구현하면 된다.

 

나는 $A$의 전체 합을 구한 다음에 뺄 때마다 전체 합에서 그 숫자를 빼는 형식으로 0배열이 되는 것을 판단했다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 32999번 Ribbon on the Christmas Present
// 구현, 브루트포스
#include <iostream>
#include <vector>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'

void solve(vector<int>& d, int start_idx, int end_idx, int m, int& ans, int& limit){
    for (int i = start_idx; i <= end_idx; i++){
        d[i] -= m;
        limit -= m;
    }
    ans++;
    return;
}

int main(void){
    fastio;
    int n; cin >> n;
    vector<int> d(n);
    int ans = 0, limit = 0;
    for (int i = 0; i < n; i++){
        cin >> d[i];
        limit += d[i];
    }
    int s, e;
    while (limit){
        bool cnt_flag = false; int m = 2'100'000'000;
        for (int i = 0; i < n; i++){
            if (!cnt_flag && d[i] > 0){
                cnt_flag = true; s = i;
            }
            else if (cnt_flag && d[i] == 0){
                cnt_flag = false; e = i-1; break;
            }
        }
        if (cnt_flag) e = n-1;
        for (int i = s; i <= e; i++){
            m = min(m, d[i]);
        }
        solve(d, s, e, m, ans, limit);
    }
    cout << ans;
    return 0;
}