백준 1439 : 뒤집기(그리디)

www.acmicpc.net/problem/1439

1439번: 뒤집기

 

Input : 0,1 문자열 S

목표 : n번 뒤집어서 1-문자열 or 0-문자열로 만드는 것

규칙 : i 번째를 잡고, 그 이후를 모두 뒤집기만 가능

Output: 최소 n  

 

i=0을 잡느냐 안잡느냐가 문제인 듯

우선 반복되는 문자열을 제거, 01010, 10101 식으로 만들어도 뒤집어야 하는 횟수는 같음

(이유: 붙어있는 000 or 111은 형태가 같이 바뀌기 때문에 몇개가 붙어있어도 상관이 없음)

len(S)//2이 정답임

if __name__=='__main__':
    S = list(input())
    compressed_S = S[0]
    char = S[0]
    while S:
        if char==S[0] : S.pop(0)
        else : 
            char = S[0]
            compressed_S += char
            S.pop(0)
    print(len(compressed_S)//2)