[BOJ][Python] 백준 20365번 - 블로그2

문제 링크: https://www.acmicpc.net/problem/20365

20365번: 블로그2

---

문제 풀이

그리디 문제이다. 1번 과정을 보면 연속된 임의의 문제들을 선택할 수 있다. 따라서 일단 파란색 혹은 빨간색으로 모든 문제를 칠한다. 최솟값을 구해야하므로 파란색으로 모든 문제를 칠하고 빨간색으로 칠할 때와 빨간색으로 모든 문제를 칠하고 파란색으로 칠할 때 중에 최소가 되는 것을 택하면 된다.

예제 입력 1을 보면 BBRBRBBR은 1번 과정에 따라서 이렇게 선택할 수 있다.
BBRBRBBR
빨간색으로 밀어버리고 파란색으로 칠하는 경우는 1+3 = 4
파란색으로 밀어버리고 빨간색으로 칠하는 경우는 1+3 = 4
따라서 최소는 4이다. 근데 둘다 똑같아서 직접 예제를 만들었다.

BRRBRBRBRRBB같은 경우는 다음과 같이 칠한다.
BRRBRBRBRRBB
빨간색으로 밀어버리고 파란색으로 칠하는 경우는 1+5 = 6
파란색으로 밀어버리고 빨간색으로 칠하는 경우는 1+4 = 5
min(6, 5) = 5이다.

코드