You are given an array of integers. On each move you are allowed to increase exactly one of its element by one. Find the minimal number of moves required to obtain a strictly increasing sequence from the input.

Example

For inputArray = [1, 1, 1], the output should be

solution(inputArray) = 3.

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] array.integer inputArray

  Guaranteed constraints:

  3 ≤ inputArray.length ≤ 105,

  • 105 ≤ inputArray[i] ≤ 105.

• [output] integer

  The minimal number of moves needed to obtain a strictly increasing sequence from inputArray.

  It's guaranteed that for the given test cases the answer always fits signed 32-bit integer type.

풀이

• 문제를 이해하는 것이 중요!
• 증가하는 숫자가 무엇이든 증가하는 수열을 만들 것
• 단, 최소한의 수로 만드는 것이 목표

int solution(int[] inputArray) {
    // 증가 수열을 만들때 쓰인 수의 합
    int sum = 0;
    
    for (int i = 0; i < inputArray.length - 1; i ++) {
        // 현재 인덱스의 숫자가 다음 인덱스의 숫자보다 크거나 같을 경우
        if (inputArray[i] >= inputArray[i + 1]) {
            // 현재 숫자 - 다음 숫자 + 1 을 더해준다.
            int n = inputArray[i] - inputArray[i + 1] + 1;
            // 더한 값 갱신
            inputArray[i + 1] += n;
            // 누적
            sum += n;
        }
    }
    
    return sum;
}