[백준] 2374 - 같은 수로 만들기 (파이썬, Python)

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

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

2374번: 같은 수로 만들기

 

해당 문제는 그리디 알고리즘으로 해결하는 문제입니다.

문제에는 특별한 Add 연산이 소개되며, 이 문제의 목표는 주어진 모든 수를 같게 만들기 위한 최소한의 Add 연산 회수를 구하는 것입니다.

 

Add(i) 연산은 i번째 수와 주변 같은 숫자를 가지는 그룹의 수들을 모두 1씩 증가시키는 연산입니다.

Add 연산을 최소로 하여 모든 수를 같게 만들려면 '가장 작은 수의 그룹을 증가시켜 나가자' 와 같은 접근 방식이 필요하다고 생각했습니다.

 

위 접근 방식에 따라 아래와 같은 단계로 문제를 해결했습니다.1. 현재 목록 중 가장 작은 수의 위치와 주변 같은 수 그룹의 크기를 계산한다.2. 그룹의 바깥에 인접한 수 중 작은 수가 될 만큼 그룹에 Add 연산을 수행한다.3. 현재 그룹의 최솟값이 초기 입력의 최댓값이 될 때까지 1~2를 반복한다.

 

전체 코드

제출 언어: Python3

시간: 88ms

import sys

def findGroup(idx, target): # 가장 작은 수의 그룹을 찾는 함수
    global n, arr

    lowerBound = 0
    upperBound = n

    for i in range(idx-1, -1, -1):
        if arr[i] != target:
            lowerBound = i+1
            break
    
    for i in range(idx+1, n):
        if arr[i] != target:
            upperBound = i
            break
        
    return (lowerBound, upperBound)

def calculate(lowerBound, upperBound): # 가장 작은 수 그룹의 양옆의 수를 비교하여 그중 작은 수만큼 Add 연산을 수행하는 함수
    global n, arr, minNum, answer

    goalNum = float("inf")

    if lowerBound != 0:
        goalNum = arr[lowerBound-1]
        
    if upperBound != n and arr[upperBound] < goalNum:
        goalNum = arr[upperBound]

    for i in range(lowerBound, upperBound):
        arr[i] = goalNum

    answer += (goalNum - minNum)


if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())

    arr = [0] * n

    for i in range(n):
        arr[i] = int(sys.stdin.readline().strip())
        
    maxNum = max(arr)
    minNum = min(arr)

    answer = 0

    while minNum < maxNum: # 현재 회차의 최솟값이 초기 입력이 최댓값이 될 때까지 반복
        minNumIdx = arr.index(minNum)

        lowerBound, upperBound = findGroup(minNumIdx, minNum)

        calculate(lowerBound, upperBound)

        minNum = min(arr)

    print(answer)