[codeground] 8. 블럭 없애기

codeground - Practice - 연습문제 - 8. 블럭 없애기

문제 : https://www.codeground.org/practice/practiceProblemList

---

1. i번째 블럭 높이(h)
   a h b -> 높이가 h인 블럭 없어지는데 걸리는 시간 = h
2. i번째 블럭(h)의 양쪽 블럭이 없어지는데 걸리는 시간 중 최소값 + 1 
   a h b -> 높이가 h인 블럭 없어지는데 걸리는 시간 = (a, b 중 작은 값) + 1

i번째 블럭이 없어질 때까지 걸리는 시간은 1, 2번 중 최소값이다.

int d[n + 2];//d[i] = i번째 블럭이 없어질 때까지 걸리는 시간
즉, d[i] = min(d[i-1] + 1 , d[i+1] + 1, i번 블럭 높이) 

i 번째 블럭이 모두 없어지는데 걸리는 시간은 양쪽(i-1, i+1)에 있는 블럭이 없어지는 시간과 관계있다.
따라서 왼쪽과 자신(i-1, i), 자신과 오른쪽(i, i+1)을 비교하는 두 번의 탐색으로 d배열을 채운다.
그리고 배열의 양 끝(d[0], d[n+1])에는 0을 저장해서 가장 가장자리에 있는 블럭들은 외부 블록으로 처리, 1(0+1) 만에 없어지게 한다.

시간 복잡도는 O(N)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codeground/8.%20%EB%B8%94%EB%9F%AD%20%EC%97%86%EC%95%A0%EA%B8%B0.cpp