[Python/파이썬] 백준 2374번 같은 수로 만들기

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

 

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for i in range(n):
    a = int(input())
    if not arr or arr[-1] != a:
        arr.append(a)


def find_min(arr):  # 현재 배열에서 가장 작은 값과 그 인덱스 리턴
    min_v = int(1e9)+1
    min_idx = -1
    for i in range(len(arr)):
        if min_v > arr[i]:
            min_v = arr[i]
            min_idx = i
    return [min_idx, min_v]


ans = 0
while True:
    if len(arr) == 1:
        break
    min_idx, min_v = find_min(arr)
    if min_idx == 0:
        ans += arr[min_idx+1]-arr[min_idx]
    elif 0 < min_idx < len(arr)-1:
        ans += min(arr[min_idx-1], arr[min_idx+1])-arr[min_idx]
    else:
        ans += arr[min_idx-1]-arr[min_idx]
    arr.remove(min_v)

print(ans)

 

1. 처음에 배열을 입력받을 때, 같은 수가 인접한 경우에는 하나만 넣어준다.

2. 배열에서 가장 작은 값 a를 구해서 a와 양옆의 값 중 작은 값과의 차를 구해서 ans에 더해주고, a는 배열에서 없앤다. 사실 코드로 보면 배열에서 없애는 것이지만, 양옆의 값 중 작은 값과 동일해질 때까지 그 수에 Add() 연산을 해서 하나의 덩어리가 됐다고 생각하면 된다. 

3. 2번 과정은 배열의 길이가 1이 될 때까지 반복하면 된다. 숫자 하나는 그 숫자를 가진 모든 수의 덩어리라고 할 수 있기 때문에 arr에 숫자가 하나만 남는다면 모든 수가 동일해졌다고 볼 수 있다.