Algorithm/Solved Problems
[ Baekjoon : python ] 백준 1439번 뒤집기 - 그리디 알고리즘
leecrossun
2021. 3. 27. 00:01
 |
|
|
" 문제 "
1439번: 뒤집기
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모
www.acmicpc.net
" 아이디어 "
0과 1이 끊어지는 구간을 세어서 더 적은 구간의 개수를 출력하면 된다.
예를 들어 0001100 의 경우
000 / 11 / 00 으로 나눌 수 있고,
11 부분만 뒤집으면 되기 때문에 답은 '1' 이다.
또다른 예로 0100011010 의 경우
0 / 1 / 000 / 11 / 0 / 1 / 0 이므로
0 의 구간은 4개, 1의 구간은 3개 이므로
3번만 뒤집으면 된다.
" 코드 "
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
s = input()
l = len(s)
temp = s[0]
zero = one = 0
if s[0] == '0':
zero += 1
else:
one += 1
for i in range(l):
if s[i] != temp:
if temp == '0':
one += 1
temp = s[i]
else:
zero += 1
temp = s[i]
print(min(zero, one))
|
cs |
" 참고자료 "
반응형