11주차_#1439 뒤집기
💬 문제이해
뒤집는 행동의 최소 횟수를 출력
뒤집는 행동의 최소 횟수를 출력
뒤집는 행동 = 연속된 하나 이상의 숫자를 잡고 모두 뒤집
예시
예를 들어 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))
백준 행렬이 생각난다. 이 문제의 경우에는, 왼쪽 상단에 위치할 수록, 더 바뀔 가능성이 없는게 greedy 로 최적해를 찾을 수 있음을 보장했다. 다만, 이 뒤집기 문제는 연속된 부분수열을 자유롭게 지정할 수 있어서 이 문제랑 비슷한 방식으로 최적해를 보장하지 않을 것 같다.
최대한 '같은 숫자끼리 뭉쳐있는 부분수열의 갯수'가 많은 숫자로 통일되는 결과물을 정답 타겟으로 생각해야한다.
ex) 0001100 의 경우 0부분순열은 2개, 1부분순열은 1개이므로 0으로 통일시키는 00000000을 정답 타겟으로 잡아야 하나?
어 그러면 차례로 "같은 숫자끼리 뭉쳐있는 부분순열의 갯수" 중 제일 적은 것을 리턴하면 이게 정답 아닌가? 보장할 수 있나? 중간중간 바뀔때에 따라서 최적해가 아닐 가능성은 없나?
최적해 검증은 !! 못하겠다 헤헤.. 그래도 일단 코드로 만들어봐야지
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))
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))
마지막 원소들 보정해줬다!
Author And Source
이 문제에 관하여(11주차_#1439 뒤집기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yesterdaykite/11주차뒤집기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)