문제 요약 및 풀이
처음에 어? 그냥 앞에서부터 버블 소트처럼 하면 되는거 아니야?
라는 단순한 생각을 했고, 그냥 제출했는데 바로 WA를 받았다.
골드가 그렇게 간단하지는 않죠? (ㅋㅋㅋ)
바로 떠오른 반례는 이거다
1
2
3
5
1 2 3 4 5
4
앞서 말한 풀이로는 2 3 4 5 1이 나오는데, 사실 답은 5 1 2 3 4 이다.
이 반례를 보면서 생각이 났다.
1
2
3
4
1. 아무튼 일단 앞에서부터 가장 큰 숫자를 채워넣야 한다.
2. 근데, 정해진 코스트가 있다.
3. 그럼? 정해진 코스트 내에서 가져올 수 있는 가장 큰 숫자를 가져오고 대체하자.
4. 이걸 앞에서부터 차례대로 하면 되겠지?
이 아이디어를 그대로 코드로 바꿨다. 그리고 AC
풀이 코드
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
n = int(input())
L = [*map(int, input().split())]
s = int(input())
cur_idx = 0
while s > 0 and cur_idx < n:
cur_item = L[cur_idx]
max_item_idx = cur_idx
max_item = L[cur_idx]
for i in range(cur_idx, min(cur_idx + s + 1, n)):
if cur_item < L[i] and max_item < L[i]:
max_item = L[i]
max_item_idx = i
cost = max(0, max_item_idx - cur_idx)
if cost <= s:
if cur_idx != max_item_idx:
s -= cost
L = L[:(cur_idx)] + [L[max_item_idx]] + L[cur_idx:max_item_idx] + L[(max_item_idx+1):]
cur_idx += 1
print(*L)
끝