[그리디 알고리즘] 1439번 - 뒤집기

[백준] 1439번 - 뒤집기

1) 문제 해결 아이디어

아이디어는 쉽게 떠올렸다.

0과 1로만 이루어진 문자열에서 변화 횟수(cnt)를 세는 것이 포인트다.

 

예를 들어, 변화 횟수와 뒤집어야하는 최소 횟수는 다음과 같다.

문자열(s)	변화 횟수(cnt)	최소 뒤집기 횟수
0	0	0
01	1	1
010	2	1
0101	3	2
01010	4	2

 

(변화 횟수(cnt) + 1) // 2 가 최소 뒤집기 횟수이다.

 

2) 소스코드

s = input()  # 0, 1로 구성된 문자열
cnt = 0      # 변화 횟수

for i in range(len(s) - 1):
  # 이전 숫자와 현재 숫자가 다를 경우
  if(s[i] != s[i+1]):
    cnt += 1  

print((cnt + 1) // 2)