[알고리즘] 백준 1439 뒤집기 / python, greedy

https://www.acmicpc.net/problem/1439

1439번: 뒤집기

 

✔ 풀이과정

예시의 0001100은 010으로 봐도 무방하다. 길이에 관계없이 문자가 바뀌는지만 보기 때문이다.

다음은 길이에 따라 최소 몇번 바꿔야하는지를 적은것이다.

0 과 1 👉 0번, 길이 1

01 👉 1번, 길이 2

010 👉 1번, 길이 3

0101 👉 2번, 길이 4

01010 👉 2번, 길이 5

010101 👉 3번, 길이 6

0101010 👉3번, 길이 7

이 규칙성을 따라서 코드를 짜면 된다.

S = input()
count = 0
for i in range(len(S)-1):
    if S[i] != S[i+1]:
        count += 1
print((count + 1) // 2)