1439번: 뒤집기
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
S = input()
zero = 0
one = 0
prev = S[0]
if prev == '0':
zero+=1
else:
one+=1
for i in range(1, len(S)):
if S[i] != prev:
if S[i] == '0':
zero+=1
else:
one+=1
prev = S[i]
print(min(one, zero))
|
cs |
이전 문자가 0인지 1인지 기록해뒀다가 문자가 바뀌면 0으로 바뀌었는지 1로 바뀌었는지에 따라 0으로 바뀐 횟수, 1로 바뀐 횟수를 누적시킨 후,
둘 중 더 작은 값을 출력.
그리디 분류에서 제대로 푸는 문제가 거의 없는데 이 문제는 그리디에서 처음으로 느껴보는 순한맛..