알고리즘/BOJ

[BOJ] 1439 - 뒤집기

서노리 2022. 1. 4. 04:49
반응형

https://www.acmicpc.net/problem/1439

 

1439번: 뒤집기

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

www.acmicpc.net

import sys
data = sys.stdin.readline().rstrip()

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로 바꾸는 경우 중에서 더 적은 횟수를 가지는 경우를 계산하면 된다.  count0과 count1은 각각 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우의 수 이다.  

 

 

s = input()
change = 0
for i in range(len(s)-1):
  if s[i] != s[i+1]:
    change += 1
if change % 2 == 0:
  result = change // 2
else:
  result = change // 2 + 1
print(result)

다른 분들의 코드를 확인해보니 이 방법 말고도 수학적인 방법으로 구현할 수도 있었다.

숫자가 변하는 개수를 2로 나누어서 뒤집는 최소 횟수를 구할 수 있다. 다만 변화 개수가 홀수인 경우에는 1을 더해줘야한다.

반응형