[백준 28433] 게리맨더링 [Python]

백준 28433 - 문제

백준 28433 - 입/출력

---

풀이

양수구간의 갯수가 음수구간의 갯수보다 많은지 판별하는 pure greedy 문제이다.

양수/음수구간에 대해 최대 구간을 구하기 위한 조건을 생각해보자.

 

먼저 양수구간의 경우 두 양수는 각각의 구간을 가지는 것이 좋다.

만약, 음수구간이다가 양수 또는 0을 만났을 경우 해당 구간을 합쳐 양수로 만들어 음수구간의 수를 최소화 할 수 있다면 합쳐야 한다.

음수구간에 대해서는 최대한 음수끼리는 합쳐야 한다.

만약 양수구간이다가 음수 또는 0 을 만났고, 합쳐서 양수구간으로 만들지 못한다면, 분리해야한다.

양수/음수구간의 판단은 이전구간의 합과 현재 요소의 값을 통해 최적으로 판단해야 되기 때문에 합는 경우는 단순히 이전 구간에 현재 구간의 값만 더해준 후 다음으로 넘어가면 된다.

 

또한, 요소 자체가 0인 경우는 양수/음수 가 아니므로 넘어가주자.

이미 위에서 특정 조건에 구간의 합이  0인 경우에 대해서도 최적으로 처리를 해주었기 때문이다.

 

만약 위의 과정을 진행했다면, 마지막 구간에 다음 비교대상이 없어 대해 양수/음수 판단이 되지 않았을 것이다.

구간의 합을 가지고 구간을 정해주자.

위의 조건을 아래와 같이 단축시킬 수 있다.

---

소스코드

소스코드 보기

---

출처

28433번: 게리맨더링