[백준] [파이썬] [그리디] 1439번: 뒤집기

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

1439번: 뒤집기 문제보기

문제

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.

예를 들어 S=0001100 일 때,

1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.

문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

예제 입력 1

0001100

예제 출력 1

1

예제 입력 4

11001100110011000001

예제 출력 4

4

---

역시 쉽지 않다.

string을 for문으로 돌려서
0 -> 1 또는 1 -> 0 으로 바뀔 때마다 cnt+=1을 해준다.
cnt로 숫자가 바뀌는 횟수를 담는다.
0 또는 1 둘 중 하나로만 바꾸면 되기 때문에 2로 나누어준다. 즉, (count+1)//2를 해준다.

과정을 시각화 하자면

입력받은 string -> 숫자 변화 횟수 -> 뒤집어야할 횟수

# 0 -> 0 -> 0 : 숫자를 바꿀필요없다

# 01 -> 1 -> 1 : 0에서 1로 숫자가 바뀌었다.

# 010 -> 2 -> 1 : 0에서 1로, 1에서 0으로 2번 바뀌었다. 이걸 +1 나누기 2 해준다

# 0101 -> 3 -> 2 : 0에서 1로, 1에서 0으로, 0에서 1로 3번 바뀌었다. 이걸 +1 나누기 2 해준다

# 01010 -> 4 -> 2 : (4+1)//2 = 2

# 010101 -> 5 -> 3 : (5+1)//2 = 3

즉, 변화 횟수(cnt) +1 하고 2로 나누서 몫을 가져오면 뒤집어야 할 최소 횟수가 나온다.

---

정답

import sys

sys.stdin=open('input.txt','r')

if __name__=="__main__":
    inputs=input()

    cnt=0
    for i in range(len(inputs)-1):
        if inputs[i] != inputs[i+1]:	# 현재 값이 이후 값과 다르면 
            cnt +=1 					# 0에서 1로 또는 1에서 0으로 바뀌었으면 카운트

    print((cnt+1)//2)

 

---