99클럽 코테 스터디 16일차 TIL: 그리디의 사고방식

오늘의 문제: 2847. 게임을 만든 동준이

단순한 그리디 문제로 보인다. 사고의 흐름을 먼저 정리해보기로 했다.

1. 배열을 순회하기 편하도록 반대로 정렬하여 접근한다.
2. 현재 있는 위치의 값을 저장하고, 다음 값으로 넘어간다.
3. 저장한 값보다 탐색한 값이 작아지도록 값을 빼준다.
4. 빼는 값들의 합이 정답이다.

이렇게만 접근한다면 문제없이 해결할 수 있을 것이라는 생각이 든다.

n=int(input())
l=[int(input()) for i in range(n)]
l.reverse()

value=l[0]
del l[0]

sum=0

for i in l:
    if value>i:
        value=i
    else:
        temp=i-value+1
        sum+=temp
        value=i-temp
print(sum)

확실히 그리디 하위 문제는 쉽게 풀린다. 이번에는 그리디의 취지에 맞게 탐욕적으로 알고리즘을 찾아 나서면서도 그 근거를 명확히 했다는 점에서 의의가 있다고 생각한다. 더 고티어 문제에서도 이렇게 문제를 해결할 수 있도록 근거 세우는 연습을 해야겠다.

오늘의 회고

그리디를 처음 시작해서 그런지는 몰라도 요새 올라오는 문제들이 굉장히 쉽다고 느껴진다. 다만 다들 근거가 명확한 정석 그리디 문제들이라 해결하면서 성장한다는 생각들이 들기는 한다.

졸리다고 그리디 문제를 대충 후려지지 말고 근거를 잡는 연습을 확실히 하자.