2847번: 게임을 만든 동준이
학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
N = int(input())
scores = [int(input()) for _ in range(N)]
if N == 1:
print(scores[0])
scores.reverse()
result=0
for i in range(1, len(scores)):
if scores[i] >= scores[i-1]:
result+=scores[i] - scores[i-1] + 1
dif = scores[i] - scores[i-1] + 1
scores[i]-=dif
print(result)
|
cs |
전체 스코어를 뒤집는다. 뒤집힌 스코어의 첫번째는 가장 마지막 레벨이므로 가장 높은 점수여야한다.
두번째 요소부터 이전 요소와 비교하여 이전 요소보다 큰 경우, 이전 요소 보다 1 적도록 수를 변경하고, 변경된 수만큼 결과를 누적시킨다.
예를들어, 최초로 입력받은 스코어가 [9, 3, 18, 6, 5] 라면 이걸 뒤집으면 [5, 6, 18, 3, 9] 가 되며 배열의 첫번째 요소인 5는 가장 마지막 레벨의 점수이므로 2번째부터 마지막 까지는 모두 5보다 작아야한다.
뒤집은 스코어 를 순회하였을때 두번째 요소가 6이므로 이전 요소인 5보다 크다.
이 경우, 6-5+1 을 하면 2가 되며 2를 빼주면 5보다 1작은 4가 된다. 뺀만큼 결과에 누적하면서 이 과정을 반복하면 아래와 같이 된다.
최초입력: [9, 3, 18, 6, 5]
뒤집은후: [5, 6, 18, 3, 9]
loop 1: [5, 4, 18, 3, 9]
loop 2: [5, 4, 3, 3, 9]
loop 3: [5, 4, 3, 2, 9]
loop 4: [5, 4, 3, 2, 1]
최종 결과: 26
오랜만에 그리디 순한맛.