문제 요약 및 풀이
문제를 간단?하게 요약/번역해보자.
1
2
3
땅의 높이를 나타내는 숫자 n개가 주어진다.
각 땅의 높이를 낮추거나 높일 수 있을 때, "가장 높은 땅의 높이"와 "가장 낮은 땅의 높이"의 격차를 17보다 작거나 같게 만들어야 한다.
이때, 총 비용을 구해야 한다. 단, 각 땅의 높이를 k만큼 낮출 때 비용은 k*k이다.
얼핏보면 심플해보이지만, 아래 테케와 같은 경우
1
2
3
4
5
6
5
2
3
20
21
24
작업 후, 전체 높이가 [4, 4, 20, 21, 21] 와 같이 될 때 최소다. 특정 최소 지점과 최대 지점만 잡고 계산하면 안 된다는 의미이다.
(제 풀이는 다른 분들의 풀이와 다른 것 같다; 문제 풀이 보기를 하니 제가 너무 꼬아서 풀었던 것 같다 ㅠ)
그래서 일단 정렬을 기본으로 하고,
두 왼쪽, 오른쪽 구간을 설정하고, 각각의 구간에 포함되어있는 숫자는 모두 같다고 가정했다.
왼쪽 구간은 무조건 증가시키는 구간, 오른쪽 구간은 무조건 감소시키는 구간으로 생각하였고, 아직 왼쪽 구간과 오른쪽 구간의 격차가 17 이상이라면 증가/감소 액션을 수행했다.
증가, 감소를 수행하는 기준은 (증가/감소시키므로서 될 코스트 - 현재까지의 코스트)를 구해서 더 코스트가 작은 액션을 수행하게 했습니다.
풀이 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
n = int(input())
height = sorted([int(input()) for i in range(n)])
cost = [0]*n
l = 0 # 왼쪽 구간은 오른쪽 끝만 알고 있으면 된다.
r = n-1 # 오른쪽 구간은 왼쪽 끝만 알고 있으면 된다.
# 초기 왼쪽 구간을 설정한다.
for i in range(n):
if height[i] == height[0]:
l = i
# 초기 오른쪽 구간을 설정한다.
for i in range(n-1, -1, -1):
if height[i] == height[-1]:
r = i
while l < r and height[r] - height[l] > 17:
l_cost = 0
r_cost = 0
# 왼쪽 구간을 증가시킴으로서 발생하는 비용 측정
for i in range(l+1):
l_cost += (cost[i]+ 1)**2 - cost[i]**2
# 오른쪽 구간을 감소시킴으로서 발생하는 비용 측정
for i in range(n-1, r-1, -1):
r_cost += (cost[i]+1)**2 - cost[i]**2
if l_cost < r_cost:
# 왼쪽 구간의 비용이 작은 경우 증가 액션 수행
for i in range(l+1):
cost[i] += 1
height[i] += 1
else:
# 오른쪽 구간의 비용이 작은 경우 감소 액션 수행
for i in range(n-1, r-1, -1):
cost[i] += 1
height[i] -= 1
# 숫자를 증가시킴으로서, 구간이 확장되어야 하는지 검사
for i in range(n):
if height[i] == height[0]:
l = i
# 숫자를 감소시킴으로서, 구간이 확장되어야 하는지 검사
for i in range(n-1, -1, -1):
if height[i] == height[-1]:
r = i
print(sum([i*i for i in cost]))
끝