Algorithm - 창고 정리(그리디)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[창고 정리]

 

창고에 상자가 일렬의 가로방향으로 쌓여 있다.

만약 가로의 길이가 7이라고 하면, 아래의 그림과 같이 1열은 높이가 6으로 6개의 상자가 쌓여 있고, 2열은 3개의 상자, 3열은 9개의 상자가 쌓여 있고 높이는 9라고 읽는다.

가로 길이가 7인 창고

 

창고 높이 조정은 가장 높은 곳에 상자를 가장 낮은 곳으로 이동하는 것을 말한다.

가장 높은 곳이나 가장 낮은 곳이 여러 곳이면 그 중 아무곳이나 선택하면 된다.

위의 그림을 1회 높이 조정하면 아래와 같아진다.

1회 높이 조정한 결과

 

창고의 가로 길이와 각 열의 상자 높이가 주어진다. m회의 높이를 조정한 후 가장 높은 곳과 가장 낮은 곳의 차이를 출력하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 창고 가로의 길이인 자연수 L(1 ≤ L ≤ 100)이 주어진다.

두 번째 줄에 L개의 자연수가 공백을 사이에 두고 입력된다. (단, 각 자연수는 100을 넘지 않음)

세 번째 줄에 높이 조정 횟수인 M(1 ≤ M ≤ 1,000)이 주어진다.

 

*출력 설명

M회의 높이 조정을 마친 후, 가장 높은 곳과 가장 낮은 곳의 차이를 출력하시오.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_28.txt', 'rt')

L = int(input())
a = list(map(int, input().split()))
m = int(input())
a.sort()

for _ in range(m):
    a[0] += 1
    a[L-1] -= 1
    a.sort()
print(a[L-1] - a[0])

# 출력 : 20

 

input_28.txt(입력)

10
69 42 68 76 40 87 14 65 76 81
50

 

 

중요내용

1. sort() 함수를 사용해서 해당 리스트의 데이터를 오름차순으로 정렬 시킨 후에 최대값에서 1을 빼고 최소값에서 1을 더하여 창고의 높이를 조정한다.
2. 위의 높이 조정행위를 50번 반복한 후에 마지막으로 최대값과 최소값의 차이를 구해주면 된다.