99클럽 코테 스터디 26일차 TIL - [백준/파이썬] - 28324 스케이트 연습

문제 링크

 

풀이

N = int(input())
arr = list(map(int, input().split()))
# 마지막 중간 지점에는 속력이 무조건 1이 되어야 하기 때문에 arr의 마지막 배열에는 1로 바꾼다
arr[-1] = 1
# 끝에서 부터 순회하면서 속력 제한과 다음 배열보다 +1 중 더 작은 것으로 갱신
for i in range(N-2, -1, -1) :
    arr[i] = min(arr[i], arr[i+1]+1)

print(sum(arr))

• 속도는 올라갈때는 제한이 없으나, 감소할때는 1씩 감소해야하는 제한이 있음
• 마지막은 속력 1
• 그렇기 때문에 마지막 -1 단계에서는 속도가 2, 1 이 되어야 하고
• 마지막 -2 에서는 3,2,1 중 하나가 되어야 함.

위 조건을 기반으로 하여 마지막 부터 순회하면서 다음 배열+1 과 속력 제한 둘 중 더 작은 값을 arr[i]에 갱신하여 arr 배열 전체의 합을 return 하는 것으로 풀이를 마무리 하겠다.

그리디 알고리즘에 대해서 아직 제대로 공부가 되지 않았다는 것을 알았고, 문제 분석에 있어서 조금 더 신중해야겠다는 생각이 들었다.