파이썬)뒤집기

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

1439번: 뒤집기

s = input()

cnt = 0

for i in range(len(s) - 1):
    if s[i] != s[i+1]:
        cnt += 1
        
print((cnt+1) // 2)

이 문제는 은근 어려웠다.

연속되는 수열의 개수를 구해야하나? 라고 생각해 연속 수열을 구하는 쪽으로 접근했다.

하지만 시간초과가 나오게 되었고 s의 길이가 100만인 것을 보아 하나의 반복문으로 수행해야 한다는 것을 생각해내 결국 다른 사람의 답을 보게 되었다.

이해는 금방 되었다.

우선 반복문을 통해 s[i]가 s[i+1]과 다른 경우 (0 => 1 or 1 => 0) cnt를 1 더해준다.

그리고 2로 나누면 된다.

왜냐하면 cnt는 다솜이가 뒤집어야 하는 횟수를 가지고 있기 때문이다..

 

무언가 현타가 오는 문제였다.