99클럽 코테 스터디 16일차 TIL: 그리디

문제

https://www.acmicpc.net/problem/2847

풀이

현재 레벨에 얻을 수 있는 점수가 다음 레벨에서 얻을 수 있는 점수 보다 크다면,
현재 레벨에서 얻을 수 있는 점수를 낮춰주면 된다.

점수를 내리는 것을 최소한으로 해야하기 때문에, 다음 레벨에서 얻을 수 있는 점수보다 1 낮게 셋팅해주면 된다.
항상 답이 존재하는 경우만 있으므로, 음수가 되는 것은 일단 생각하지 않고 풀이하였다.

그런데 이 문제는 앞에서부터 확인하는 것이 아닌 뒤에서 부터 확인해야 한다.
왜 그럴까?

예시 입력의 5, 5, 5를 확인해보자
첫번째 레벨의 점수가 5점이고, 두번째 레벨의 점수가 5점이다.
그러면 첫번째 레벨의 점수를 1 낮춰 4로 변경해주자.

그러면 다음과 같다. 4, 5, 5
두번째 레벨의 점수와 세번째 레벨의 점수도 위와 동일하다.

그러면 점수가 다음과 같이 변경될 것이다.
4, 4, 5

첫번째 점수와 두번째 점수가 같아 이는 정답을 도출할 수 없다.

뒤에서 부터 확인하면 다음과 같이 변할 것이다.
5, 5, 5 -> 5, 4, 5 -> 3, 4, 5

이를 구현한 코드는 다음과 같다.

소스코드

후기

어렵지 않게 풀 수 있는 문제였다.
점수를 내리는 것을 최소한으로 해야하기 때문에 다음 레벨의 점수보다 1만 낮춰준다는 점에서 그리디 알고리즘이라고 할 수 있다.