Q03 문자열 뒤집기

1439번: 뒤집기 (acmicpc.net)

1439번: 뒤집기

 

문자열의 특정 부분의 1/0을 반전시킬 수 있을 때 최소한의 횟수로 전체 문자열의 숫자를 같게 만드는 문제이다.

 

0과 1이 뒤집어지는 부분이 몇 개 인지 세어보면 규칙을 찾을 수 있다.

 

s = input()

n = s[0]
count = 0
for i in range(1,len(s)):
    if n != s[i]:
        n = s[i]
        count += 1
print((count+1)//2)

 

001111 처럼 한 번 꺾이면 0이나 1부분을 한 번 뒤집으면 전체를 똑같이 만들 수 있다. -> 1번

000111000 처럼 두번 꺾이면 111부분만 뒤집으면 전체를 똑같이 만들 수 있다 -> 1번

00110011 처럼 세 번 꺾이면 00,00부분이나 11,11부분을 뒤집어서 전체를 똑같이 만들 수 있다 -> 2번

0011001100 처럼 네 번 꺾이면  11,11 부분을 뒤집어서 전체를 똑같이 만들 수 있다 -> 2번

 

1,2번 꺾임 -> 최소횟수 1번

3,4번 꺾임 -> 최소횟수 2번

5,6번 꺾임 -> 최소횟수 3번

...

2*n-1, 2*n번 꺾임 -> 최소횟수 n 번