동준이가 만든 게임
면접 대비시간 제한1초메모리 제한128 MB
N개의 레벨 점수가 주어질 때 모든 점수를 양수로 유지하면서 순증가하도록 만들기 위한 최소 감소량 총합을 구합니다.
문제
동준이는 그래픽스 수업에서 배운 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 난이도 순서대로 배치된 N개의 레벨이 있고, 각 레벨을 클리어하면 정해진 점수를 얻는다. 플레이어의 총점은 클리어한 레벨들의 점수 합이며, 이 총점으로 온라인 순위를 정한다.
난이도가 높아질수록 클리어 점수도 더 커져야 한다. 하지만 일부 쉬운 레벨의 점수가 뒤에 있는 더 어려운 레벨의 점수보다 크거나 같은 경우가 생겼다.
동준이는 몇몇 레벨의 점수를 1씩 낮춰서, 첫 번째 레벨부터 마지막 레벨까지 점수가 엄격히 증가하도록 만들려고 한다. 점수는 항상 양수여야 한다. 점수를 1만큼 낮추는 것은 한 번의 감소로 센다. 가능한 조정 중 전체 감소 횟수가 최소가 되도록 할 때, 필요한 감소 횟수를 구하라. 항상 가능한 입력만 주어진다.
입력
첫째 줄에 레벨 수 N이 주어진다. (1 <= N <= 100)
다음 N개 줄에는 첫 번째 레벨부터 마지막 레벨까지, 각 레벨을 클리어했을 때 얻는 점수가 한 줄에 하나씩 주어진다. 각 점수는 20,000보다 작은 양의 정수이다.
출력
최종적으로 점수가 엄격히 증가하도록 만들기 위해 필요한 최소 감소 횟수를 출력한다.