💬 문제이해

뒤집는 행동의 최소 횟수를 출력

뒤집는 행동 = 연속된 하나 이상의 숫자를 잡고 모두 뒤집

예시

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

🙋‍♀️ 처음 든 생각

• 백준 행렬이 생각난다. 이 문제의 경우에는, 왼쪽 상단에 위치할 수록, 더 바뀔 가능성이 없는게 greedy 로 최적해를 찾을 수 있음을 보장했다. 다만, 이 뒤집기 문제는 연속된 부분수열을 자유롭게 지정할 수 있어서 이 문제랑 비슷한 방식으로 최적해를 보장하지 않을 것 같다.

• 최대한 '같은 숫자끼리 뭉쳐있는 부분수열의 갯수'가 많은 숫자로 통일되는 결과물을 정답 타겟으로 생각해야한다.
  ex) 0001100 의 경우 0부분순열은 2개, 1부분순열은 1개이므로 0으로 통일시키는 00000000을 정답 타겟으로 잡아야 하나?

• 어 그러면 차례로 "같은 숫자끼리 뭉쳐있는 부분순열의 갯수" 중 제일 적은 것을 리턴하면 이게 정답 아닌가? 보장할 수 있나? 중간중간 바뀔때에 따라서 최적해가 아닐 가능성은 없나?

• 최적해 검증은 !! 못하겠다 헤헤.. 그래도 일단 코드로 만들어봐야지

🌻 1회차 코드

arr = input()
arr_len = len(arr)

zero_cnt = 0
one_cnt = 0
cur_zero_counting = False
cur_one_counting = False

for i in range (arr_len - 2) :
  if arr[i] == '0' and arr[i+1] == '0' :  continue
  elif arr[i] == '0' and arr[i+1] == '1' :  zero_cnt += 1
  elif arr[i] == '1' and arr[i+1] == '0' : one_cnt += 1
  elif arr[i] == '1' and arr[i+1] == '1' : continue 

# 마지막 원소 보정
if arr[arr_len-2] == '0' and arr[arr_len-1] == '1' : one_cnt += 1
elif arr[arr_len-2] == '1' and arr[arr_len-1] == '0' : zero_cnt += 1
elif arr[arr_len-2] == '0' and arr[arr_len-1] == '0' : zero_cnt += 1
else : one_cnt += 1 # 마지막이 11일때

print(min(zero_cnt, one_cnt))

실패

엉엉...

두번째 코드

arr = input()
arr_len = len(arr)

zero_cnt = 0
one_cnt = 0
  
for i in range (arr_len - 2) :
  if arr[i] == '0' and arr[i+1] == '0' :  continue
  elif arr[i] == '0' and arr[i+1] == '1' :  zero_cnt += 1
  elif arr[i] == '1' and arr[i+1] == '0' : one_cnt += 1
  elif arr[i] == '1' and arr[i+1] == '1' : continue 

# 마지막 원소 보정
if arr[arr_len-2] == '0' and arr[arr_len-1] == '1' : 
  one_cnt += 1
  zero_cnt += 1
elif arr[arr_len-2] == '1' and arr[arr_len-1] == '0' : 
  zero_cnt += 1
  one_cnt += 1
elif arr[arr_len-2] == '0' and arr[arr_len-1] == '0' : 
  zero_cnt += 1
else : # 마지막이 11일때
  one_cnt += 1 

print(min(zero_cnt, one_cnt))

마지막 원소들 보정해줬다!