[Leetcode] 1526. Minimum Number of Increments on Subarrays to Form a Target Array

문제 : https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/

---

양의 정수 배열 target과 동일한 크기의 초기값이 모두 0인 initial 배열이 있다.

한 번의 연산에서 initial 배열의 하위배열의 요소값들을 1씩 증가시킬 때, initial 배열에서 target 배열로 만들 수 있는 최소 연산 횟수를 구하라.

---

결국은 어느 부분을 하위 배열로 묶을 것인지를 찾는게 중요하다.

 

target 배열을 앞에서부터 탐색하면서 이전 값 보다 탐색 중인 값이 더 큰 경우 이전 값과의 차이(하위 배열을 제외하고 추가로 증가되어야 하는 수)를 정답에 더해준다.

탐색하는 값이 이전 값보다 같거나 작다면 이전 값과 같은 하위 배열로 묶일 수 있기 때문에 이전 값에서 정답에 추가되는 수를 구할 때 현재 탐색하는 값도 같이 증가시켰다고 가정할 수 있으므로 정답과는 관계가 없다.

 

[1, 2, 3, 2, 1] 을 예시로 들어보자.

이전 값의 초기값은 0이다.

[1] -> 1 - 0 = 1 (정답에 추가)

[1, 2] -> 2 - 1 = 1 (정답에 추가)

[1, 2, 3] -> 3 - 2 = 1 (정답에 추가)

[1, 2, 3, 2, 1] -> 이전 값이 탐색하는 값보다 더 크므로 추가되는 값이 없음. 

 

 

시간복잡도는 N = |target| 이라 했을 때, O(N)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/1526.%20Minimum%20Number%20of%20Increments%20on%20Subarrays%20to%20Form%20a%20Target%20Array.cpp