[백준 2847] 게임을 만든 동준이

그리디 알고리즘으로 해결할 수 있는 문제입니다.

Key Point

본 문제에서 주목할만한 점은 다음과 같습니다.

• 임의로 정렬해서 푸는 것이 아니라, 주어진 순서 그대로 풀어야합니다.
• ‘최소한’ 으로 줄이는 방법을 찾아야합니다.

따라서, 일단 주어진 수들을 numbers라는 리스트 하나에 모두 담아놓습니다.
그 이후에, ‘맨 뒤’ 에서부터 살펴보면서
현재 살펴보는 인덱스의 요소보다 바로 앞의 인덱스의 요소가 같거나 더 크면
서로 1 차이 만 나도록 줄여주면 됩니다.
예를 들어

5 3 7 5

각 레벨의 점수가 위와 같을 때
4레벨의 점수(3번 인덱스)가 5인 반면에 3레벨의 점수(2번 인덱스)가 7이기 때문에
3레벨의 점수를 5보다 ‘1’ 낮은 4로 만드는 게 가장 최소한으로 점수를 내리는 방법입니다.
따라서 해당 점수를 내린 결과는

5 3 4 5

위와 같게 됩니다.
이후에도 차례대로 위와 같은 방식으로 점수를 줄여나가면

5 3 4 5

2 3 4 5

최종적으로는 2 3 4 5가 되어 총 ‘6’점을 내려야한다는 결론이 도출됩니다.

만약, 맨 앞에서부터 살펴보게 되면

5 5 5

위와 같은 경우에서

4 5 5

첫번째 요소가 먼저 줄어들게 되고

4 4 5

두번째 요소도 줄어들게 되어 첫번째와 두번째 요소가 모두 4로 동일하게 됩니다.
이 경우, 또 다시 이전의 요소들을 고려해주어야하기 때문에 시간이 더 들게 됩니다.
따라서, 맨 뒤에서부터 쭉 순차적으로 살피며 내려오면 한번에 결과를 도출해낼수 있습니다.
해당 코드는 다음과 같습니다.

문제 : 백준 2847 - 게임을 만든 동준이