그리디
현재 상황에서 지금 당장 좋은 것만 고르는 방법

백준 1439번

✅ 문제

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

예를 들어 S=0001100 일 때,

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

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

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

입력 예시

0001100

출력 예시

1

💻 코드

import math

data = input()

# 변경 되는 지점 수
count = 0

comp = int(data[0])
for i in range(1, len(data)):
    num = int(data[i])
    # 앞 데이터와 일치하지 않을 때 comp 변수를 다시 바꿔준다.
    if comp != num:
        count += 1
        comp = num

# 뒤집기 횟수는 count를 나누기 2한 수이다. count가 홀수 일 때는 올림 
result = math.ceil(count / 2)
print(result)

설계

변경되는 지점을 2개를 한 쌍으로 하여 그 지점을 뒤집어 주면 된다.
변경되는 지점 개수가 홀 수인 경우는 맨 처음 숫자와 맨 마지막 숫자가 서로 다른 경우이다. 이러한 경우는 변경되는 지점을 하나 더 추가하여 한 쌍으로 생각하면 된다. (문제 풀이의 경우 올림을 해주었다.)

➕ 다른 풀이

data = input()

count0 = 0
count1 = 0

if data[0] == '1':
    count0 += 1
else : 
    count1 += 1

for i in range(len(data) -1) :
    if data[i] != data[i+1]:
        if data[i+1] == '1':
            count0 += 1
        else :
            count1 += 1

print(min(count0, count1))

문자열을 전부 0으로 만드는 방법과 1로 만드는 방법 모두 count하여 최소 count를 가진 값을 출력한다.