책 314p

문제

• 입력
  • 첫째줄에 0과 1로만 이루어진 문자열 S 주어짐
  • S의 길이는 100만 보다 작음
• 출력
  • 첫째줄에 다솜이가 해야하는 행동의 최소 횟수 출력

다솜이는 0과 1로만 이루어진 문자열 S 가지고 있음.
다솜이는 S에 있는 모든 숫자를 전부 같게 만드려고 함.
다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고, 모두 뒤집는것 (0->1, 1->0)

예시) S=00011000일때
1. 전체 뒤집으면 11100111
2. 4번째부터 5까지 뒤집으면 11111111
두 번만에 모두 같은 숫자로 만들 수 있음

풀이

풀이 아이디어

전부 0으로 바꾸는 경우와, 전부 1로 바꾸는 경우 중 더 적은 횟수를 가지는 경우 계산

풀이 아이디어를 보고 든 생각

나는 먼가 결과의 형태를 두루뭉술하게 생각했는데
"결과" (행동)가 아니라 "결과의 출력형태" (행동의 최소 횟수) 가
알고리즘을 개선시키는 것 뿐만 아니라, 아예 결정할 수도 있겠구나 라는 생각을 했다.

모호하게 결과 전체를 이미지로 생각하는게 아니라
구체적이고 정확하게 결과의 '출력형태'를 목표로 생각하자

코드

data = input()
count0 = 0 #전부 0으로 바꾸는 경우
count1 = 0 #전부 1로 바꾸는 경우

# 첫번째 원소에 대하여 처리
if data[0] == '1' :
	count0 += 1
else :
	count1 += 1

# 두번째 원소부터 모든 원소를 확인하며
for i in range(len(data) - 1) :
	if data[i] != data[i+1] :
		# 다음 수에서 1로 바뀌는 경우
		if data[i+1] == '1' :
			count0 += 1

print(min(count0, count1))