[백준/2879] 코딩은 예쁘게 (Python)

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

2879번: 코딩은 예쁘게

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:17:37

 

---

 

문제 설명

 

 

백준이는 한 작은 회사에 취직했다. 이 회사에서 백준이는 소스 코드의 뒤죽박죽인 인덴트를 고치고 있다. 인덴트는 각 줄을 탭 키를 이용해 들여 쓰는 것을 말한다. 다행히 백준이가 사용하는 편집기는 연속된 줄을 그룹으로 선택하고, 여기에서 각 줄의 앞에 탭을 추가하거나, 삭제할 수 있다. 백준이를 도와 코드의 뒤죽박죽인 인덴트를 예쁘게 고치는 방법을 생각해보자.

줄의 개수 N과 각 줄의 앞에 있는 탭의 개수와 올바른 탭의 개수가 주어진다. 이때, 한 번 편집을 할 때, 다음과 같은 명령을 수행할 수 있다.

연속된 줄을 그룹으로 선택한다.
선택된 줄의 앞에 탭 1개를 추가하거나 삭제한다.
위의 두 명령을 모두 수행하는 것이 하나의 편집이며, 선택된 줄의 개수와는 상관이 없다. 만약, 선택한 줄 중에 단 한 줄이라도 탭이 없을 경우에는, 탭을 삭제하는 명령을 수행할 수 없다.

백준이가 몇 번 편집 만에 코드의 인덴트를 올바르게 고칠 수 있는지 구하는 프로그램을 작성하시오. 이때, 편집 회수의 최솟값을 구해야 한다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 줄의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 현재 줄에 있는 탭의 개수가 주어지며, 1번째 줄부터 순서대로 주어진다. 탭의 개수는 0보다 크거나 같고, 80보다 작거나 같은 정수이다. 셋째 줄에는 각 줄의 올바른 탭의 개수가 주어진다. 1번째 줄부터 순서대로 주어지며, 이 값도 0보다 크거나 같고, 80보다 작거나 같은 정수이다.

 

출력

 

첫째 줄에 코드의 인덴트를 올바르게 고치는 편집 회수의 최솟값을 출력한다.

 

입력 예시

 

4
1 2 3 4
3 1 1 0

 

출력 예시

 

6

 

 

---

 

풀이

 

DP라고 생각하고 풀이했는데, 부분 최적해가 전체 최적해로 이어지므로 그리디에 더 가깝지 않을까 싶다.

 

1번부터 i번까지의 최소 인덴트 횟수를 DP[i]라고 두고, i번째 올바른 탭과 현재 탭의 차를 diff[i]라고 두자. 우리는 i+1번째 줄과 목표가 주어졌을때, 이 최소 편집 횟수를 어떻게 업데이트할지 궁금하다.

 

• diff[i]와 diff[i+1]의 부호가 다를 경우 : 이 경우는 앞선 최소 편집 횟수와 교집합이 발생할 수 없다(방향이 다르기 때문), 즉 i+1번째 줄에 대해서만 탭 조정을 시행해야 한다. 따라서 DP[i+1] = DP[i] + abs(diff[i+1])을 만족한다.
• diff[i]와 diff[i+1]의 부호가 같을 경우 : 이 경우는 i번째 줄 조정 작업에 i+1번째 줄 조정이 포함될 수 있음을 의미한다. 이 경우는 다음과 같은 두 가지 상황이 있을 수 있다.
  • abs(diff[i]) <= abs(diff[i+1]) : 즉 i번째까지의 줄 조정에 더해 i+1번째는 추가적인 줄 조정을 요구하는 상황이다. 따라서 DP[i+1] = DP[i] + abs(diff[i+1]) - abs(diff[i]) 가 된다.
  • abs(diff[i]) > abs(diff[i+1]) : i+1번째 줄 조정 작업이 이전 작업에 완전히 포함될 수 있으므로, 이 작업은 무시되어도 된다. 따라서 DP[i+1] = DP[i] 가 된다.
  • 위 두 작업을 한 수식으로 합치면, DP[i+1] = DP[i] + max(0, abs(diff[i+1]) - abs(diff[i])) 로 나타낼 수 있겠다.

모든 경우에 대해 위 계산을 시행하면, 마지막에 최소 편집 횟수가 저장된다. 이를 출력하면 된다.

 

풀이 코드

N = int(input())
cur_list = list(map(int, input().split()))
target_list = list(map(int, input().split()))
diff_list = [ target_list[i] - cur_list[i] for i in range(N) ]
dp = [0]*N
dp[0] = abs(diff_list[0])

for i in range(1, N) :
  if diff_list[i] * diff_list[i-1] > 0 :
    dp[i] = dp[i-1] + max(0, abs(diff_list[i]) - abs(diff_list[i-1]))
  else :
    dp[i] = dp[i-1] + abs(diff_list[i])

print(dp[-1])

풀이 완료!