[python] baekjoon 2879 풀이

문제

문제 링크 -> https://www.acmicpc.net/problem/2879

2879번: 코딩은 예쁘게

 

문제풀이

문제를 보면 최대한 많은 줄에 탭을 추가하거나 삭제해야 최솟값으로 일을 끝낼 수 있다.각 줄에서 어떤 행동을 해야하는지 알아내기 위해서 첫째 줄을 둘째 줄에 있는 값으로 빼주면 각 줄에서 해야할 행동을 구할 수 있다.양수가 있으면 탭을 추가해야하는 부분이고 음수가 있으면 제거해야하는 부분이다. 

 

반복문을 통해 첫 줄부터 끝까지 탐색해간다. 만약 현재 줄이 이전 줄과 같은 행동을 한다면 묶어서 처리하고, 다른 행동을 해야한다면 두 줄은 한번에 묶어서 처리할 수 없는 부분이기에 나눠서 처리해야 한다. 행동이 같을 때는 계속 전진하면서 같이 처리할 부분들을 모아뒀다가 다른 행동을 해야하는 줄이 나오면 이때까지 모아둔 줄을 한번에 처리하는 코드를 작성하면 된다.

 

이때 모아둔 줄을 최소한의 연산으로 처리하기 위해서 최솟값을 찾고 분할정복을 하는 방법으로 문제를 해결할 수 있다.모아둔 줄들은 모두 같은 연산을 수행해야하기 때문에 최솟값만큼은 무조건 다같이 실행된다는 것을 알 수 있다.최소값만큼 처리한다면 최솟값의 연산만 필요한 줄은 더이상 어떠한 연산도 하면 안되기에 그 부분을 중심으로 두개로 나눈다.그리고 다시 최솟값을 찾고 두개로 나누는 연산을 계속하면 모든 줄이 올바른 인텐트의 수를 갖게 된다.

 

코드

import sys

def calCount( differences ) :

    if not differences :
        return 0

    if len(differences) == 1 :
        return differences[0]

    minVal = min(differences)
    minIdx = differences.index(minVal)

    cnt = minVal
    cnt += max(0, calCount(differences[:minIdx]) - minVal)
    cnt += max(0, calCount(differences[minIdx+1:]) - minVal)

    return cnt

# 1개
N = int(sys.stdin.readline().rstrip())

now = list(map(int,sys.stdin.readline().rstrip().split()))
right = list(map(int,sys.stdin.readline().rstrip().split()))

difference = [ x1-x2 for x1,x2 in zip(now,right)]

prev_sign = difference[0] > 0
same = []
answer = 0

# sign : True == + , False == -
for idx, diff in enumerate(difference) :

    now_sign = diff > 0

    if prev_sign == now_sign :
        same.append(abs(diff))

    else :
        answer += calCount(same)
        same = []
        same.append(abs(diff))
        prev_sign = now_sign

answer += calCount(same)

print(answer)

 

초기 접근 방식과 오답의 원인

같은 작업을 수행해야하는 줄들을 모으는 방법은 생각했지만

모아진 줄들에서 최솟값을 찾기위해 분할 정복으로 해결하는 방법은 생각해내지 못하고 시간초과가 났었다.

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.