[백준] 2879 코딩은 예쁘게

2879번: 코딩은 예쁘게

문제 확인

 

특별한 알고리즘이 필요 없는 구현 문제입니다.

 

풀이

 

먼저 값을 쉽게 비교하기 위해서 "현재 탭의 수 - 올바른 탭의 개수"로 배열에 저장합니다.

 

4

1 2 3 4

3 1 1 0

위와 같은 경우 배열에는 -2 1 2 4 로 저장 될 것입니다.

 

문제에서 주어진 조건에 따라 연속된 줄을 한번에 편집이 가능하며 주의해야 할 점은 편집할 때 추가, 삭제 중 한가지만 가능하다는 것입니다. 따라서 -2, 1 를 그룹으로 선택하여 편집하는 것 보다 양수, 음수 끼리 그룹을 만들어 편집을 하는 것이 유리합니다. 

 

그룹으로 나눈 후 같은 부호의 수 끼리 비교를 할 때 2가지 경우로 나눌 수 있습니다.

• 다음 수가 현재 수 보다 클 때(ary[i-1] < ary[i]) : 이 경우 다음 수를 편집하는 도충에 이전 수를 편집 완료 할 수 있습니다. 3, 5, 8 수가 있을 때 모든 수를 3번 편집 하면 0, 2, 5 가 되고, 남은 2, 5를 2번 편집하면 3이 남아 총 2+3+5, 즉 8번, ary[i] 번으로 편집으로 완료할 수 있습니다. 즉 계속해서 이 경우만 나올경우 마지막 수 만큼 편집을 하면 됩니다.
• 다음 수가 현재 수 보다 작을 때(ary[i-1] > ary[i]) : 이 경우 이전 수를 처리하기 위해서는 앞의 수를 처리한 후 남은 차이만큼 더 편집을 해야 하기 때문에  | ary[i]-ary[i-1] | 이 됩니다.
• 수가 같은 경우 그룹으로 묶어서 처리하기 때문에 고려하지 않아도 됩니다.

 

코드

#include <cstdio>
#define absol(x) (x&0x80000000 ? -(x) : x)
using namespace std;
int main() {
    int n;
    int ary[1000];
    scanf("%d", &n);
    for (int i = 0; i < n; i++) 
        scanf("%d", &ary[i]);
    for (int i = 0; i < n; i++) {
        int t;
        scanf("%d", &t);
        ary[i] -= t;
    }
        
    int count = absol(ary[n - 1]), prev = ary[0];
    for (int i = 1; i < n; prev = ary[i++]) {
        if ((ary[i] ^ prev) < 0)//부호가 바뀌는 경우
            count += absol(prev);
        else if((ary[i] ^ (ary[i] - prev)) < 0)//== |ary[i-1]| < |ary[i]|
            count += absol(ary[i] - prev);
    }
    printf("%d", count);
}