220510 - 같은 수로 만들기

◾ 같은 수로 만들기 : 백준 2374번

• https://www.acmicpc.net/problem/2374

문제

n(1 ≤ n ≤ 1,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다. 이 자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가한다. 이때, A[i]만 증가하는 것이 아니고, A[i]의 좌우로 인접한 같은 수의 그룹이 한번에 1씩 증가한다. A[1]과 A[n]은 인접해 있지 않다.

예를 들어 수가 {1, 1, 1, 1, 3, 3, 1} 이었다고 해 보자. Add(2)를 하면 A[2]의 좌우로 인접한 같은 수가 1씩 증가하니까 {2, 2, 2, 2, 3, 3, 1}이 된다. 여기서 Add(4)를 하면 {3, 3, 3, 3, 3, 3, 1}이 되고, 여기서 Add(1)을 하면 {4, 4, 4, 4, 4, 4, 1}이 된다.

이와 같이 Add라는 연산을 사용하여 A[1] = A[2] = A[3] = … = A[n]이 되도록 하려 한다. 이때, 최소 회수로 Add연산을 사용하는 방법을 찾는 것이 문제이다.

---

입력

• 첫째 줄에 정수 n이 주어진다. 다음 n개의 줄에는 차례로 A[1], A[2], …, A[n]이 주어진다. 모든 입력은 1,000,000,000을 넘지 않는다.
  • n(1 ≤ n ≤ 1,000)

출력

• 첫째 줄에 최소의 Add연산 사용 회수를 출력한다. 이 값은 10^25을 넘지 않는다.

입출력 예

Input	Output
3 1 5 10	9

---

◾ 풀이

1. 해설

• 인접한 같은 수가 같이 오르기 때문에 리스트의 최대값으로 만드는 것이 최소 횟수이다.
• 최대값을 기준으로 왼쪽, 오른쪽으로 분할하여 횟수를 계산하면 된다.
  • 최대값 max => [왼쪽을 max로 만들기 위한 횟수 + 오른쪽을 max로 만들기 위한 횟수]
  • 왼쪽, 오른쪽의 원소가 1개 이하일 경우까지 분할하여 차례로 계산한다.

---

2. 프로그램

1. n, num_list 입력
2. make_same_num 함수
   • 리스트의 길이가 0이면 None 반환
   • 그렇지 않다면, 최대값 반환
   • 최대값 기준 : 왼쪽, 오른쪽을 최대값으로 만들기 위한 횟수 계산

# 코드
n = int(input())

num_list = [int(input()) for _ in range(n)]
result = 0

def make_same_num(num_list):
    global result
    size = len(num_list)
    if size == 1:
        return num_list[0]
    if size == 0:
        return None
    
    max_num = max(num_list)
    max_index = num_list.index(max_num)

    left_max = make_same_num(num_list[:max_index])
    right_max = make_same_num(num_list[max_index+1:])

    if left_max is not None:
        result += max_num - left_max
    if right_max is not None:
        result += max_num - right_max

    return max_num

make_same_num(num_list)

print(result)