[Python] 백준 2879번: 코딩은 예쁘게

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

2879번: 코딩은 예쁘게

1. 출발탭과 목표탭의 차를 구하고 양수와 음수의 그룹을 분리해준다. (양수와 음수의 분리를 위해, 양수와 음수를 같이연산하면 반대연산은 자꾸 늘어나기때문 ex) 1 -1 에 + 1 을하면 2 0 즉 음수는 사라졌지만 양수의 연산은 하나 더 늘었다)

2. 제일 작은수를 기준으로 분할해서 재귀를 돌려준다. ex) 3 2 1 2 3 (-1) > 2 1 0 1 2   0을 기준으로 분리

3. 길이가 0이거나 1일때까지 분할한다. (1자리에서 분할할경우 음수의값이 나오기때문에 최솟값을 0 으로 해준다)

 

n = int(input())
s, e = list(map(int, input().split())), list(map(int, input().split()))
diff = list(x-y for x, y in zip(s, e))
op = diff[0] > 0
tmp = []
ans = 0


def countIntent(x):
    if len(x) == 0:
        return 0
    elif len(x) == 1:
        return x[0]
    else:
        minValue = min(x)
        idx = x.index(minValue)
        cnt = minValue
        cnt += max(0, countIntent(x[:idx]) - minValue)
        cnt += max(0, countIntent(x[idx+1:]) - minValue)
    return cnt


for x in diff:
    if (x > 0) == op:
        tmp.append(abs(x))
    else:
        op = not op
        ans += countIntent(tmp)
        tmp = [abs(x)]

ans += countIntent(tmp)

print(ans)