[백준][Python] 2374 같은 수로 만들기

풀이 1.

극소점부터 큰값이 나올때마다 그만큼 채워주면서 연산.

 

import sys
input = sys.stdin.readline

n = int(input())
cnt = 0
stack = [int(input())]
max_num = stack[-1]
for _ in range(n - 1):
    num = int(input())
    if stack[-1] < num:
        cnt += num - stack[-1]
        max_num = max(max_num, num)
    stack.pop()
    stack.append(num)
cnt += max_num * len(stack) - sum(stack)
print(cnt)

 

풀이2.

분할정복으로 max_idx를 pivot으로 좌우 분할 해 각 구간의 연산값을 더해주며 최상단까지 올라온다.

import sys
input = sys.stdin.readline

def count_add(nums, prev_max):
    if not nums:
        return 0

    max_val = 0
    min_val = float('inf')
    for i in range(len(nums)):
        if max_val < nums[i]:
            max_val = nums[i]
            max_idx = i
        min_val = min(min_val, nums[i])
        
    if max_val == min_val:
        return prev_max - max_val
    
    result = count_add(nums[:max_idx], max_val) + prev_max - max_val + count_add(nums[max_idx+1:], max_val)
    return result