[BOJ/백준][Gold2] 2879 : 코딩은 예쁘게 (C++)

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

2879번: 코딩은 예쁘게

 

 

[난이도] Gold2
[유형] Greedy

[풀이]
우선 배열에 현재 (현재 탭 개수 - 목표 탭 개수) 를 저장해줍니다.
배열에서 양수인 것들은 탭을 빼줘야 하는 것들이고
음수인 것들은 탭을 더해주야 하는 것들입니다.

잘 생각해보면 부호가 같은 연속된 수열에서 절댓값이 가장 작은 값만큼 탭을 제거하거나 추가하는
연산을 하는게 가장 효율적인 연산입니다.

전체 수열이 0이 될때까지 루프를 돌면서 수열 전체를 확인하면서 위의 방법으로 탭을 추가하거나 제거해주면 됩니다.

 

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int N,a[1001];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    for(int i=0;i<N;i++) {
        int v;
        scanf("%d",&v);
        a[i]-=v;
    }
    int ans=0;
    bool ok=1;
    while(ok){
        ok=0;
        for(int i=0;i<N;i++){
            if(!a[i]) continue;
            ok=1;
            int minv=a[i];
            for(int j=i+1;j<=N;j++){
                if(a[i]*a[j]>0){
                    if(abs(a[j])<abs(minv)){
                        minv=a[j];
                    }
                }else{
                    ans+=abs(minv);
                    for(int k=i;k<j;k++) a[k]-=minv;     
                    i=j-1;
                    break;
                }
            }
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/2879.cpp