editorial

---

D

summary:

0,1,2 중에 하나가 적힌 배열이 있는데, 전부 파란색이다.

파란색 중 하나를 빨간색으로 바꾸는데 1의 비용이 든다.

1 이상의 수를 가지고 있는 빨간색인 원소와 인접한 파란색 원소를 빨갛게 칠하는 데는 빨간색 원소의 숫자를 하나 줄여서 0의 비용으로 바꿀수 있다.

solution:

1의 비용으로 다 칠할 수 있는 구간의 개수를 최소화해서 나누면 된다.

1의 비용으로 칠할 수 있는 구간이 될 조건:

• 구간의 중간에 0이 있으면 안됨
• 구간의 시작하는 수가 0이면서 구간의 최댓값이 2이면 0으로 끝날 수 있음
• 구간의 시작하는 수가 1이상이면 0으로 끝날 수 있음
• 그렇지 않으면 0으로 끝날수 없음

따라서 구간의 시작하는 부분의 수와, 구간 내의 최댓값을 저장하고 0을 만나면 구간에 포함 가능한지 고려하고, greedy 하게 몇 개의 구간으로 나눌 수 있는지 구하면 된다.