[백준/BOJ] 2879 코딩은 예쁘게

문제 : 2879 코딩은 예쁘게

2879번: 코딩은 예쁘게

소스코드의 현재 탭의 개수와 원하는 탭의 개수가 주어질 때,

연속된 줄을 그룹을 선택해 편집하는 최소 횟수를 구하는 문제이다.

 그리디 알고리즘을 활용해 한번 탭을 추가하거나

삭제할 때 현재 줄부터 가장 뒤의 줄까지 중 가장 많은 탭 개수를

한 번에 조절할 수 있는 위치를 찾아 처리해주는 것을 반복하면 된다.  

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, ans, arr[1005], tab[1005];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i=0;i<N;i++){
        cin >> arr[i];
    }
    for (int i=0;i<N;i++){
        cin >> tab[i];
    }
    for (int i=0;i<N;i++){
        while (arr[i]!=tab[i]){
            ll gap=0, max=0, cnt=0, chk=i;
            arr[i]<tab[i] ? gap=1 : gap=-1;
            for (int j=i+1;j<N;j++){
                if (arr[j]+gap<0)
                    break;
                if ((arr[j]>tab[j] && gap==-1) || (arr[j]<tab[j] && gap==1))
                    cnt++;
                else
                    cnt--;
                if (cnt>max){
                    max=cnt;
                    chk=j;
                }
            }
            for (int j=i;j<=chk;j++)
                arr[j]+=gap;
            ans++;
        }
    }
    cout << ans;
    return 0;
}