백준 1439 - 파이썬

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

1439번: 뒤집기

문제 풀이

이 문제의 아이디어는 금방 떠올릴수 있었다.

S=0001100 일때 연속된 숫자는 묶어서 같이 뒤집기 때문에 연속된 숫자는 하나로 취급할 수 있다.

ex) 0001100 -> 010

 

아이디어 떠올리자마자 바로 코드 구현을 해 보았고, 정답까지 거의 작성이 가능했다.

n = input()

cnt = 0

for i in range(len(n)-1):
  if n[i] != n[i+1]:
    cnt +=1

print(cnt)

이 코드의 아쉬운점은 0001100과 같이 숫자가 두번 바뀔때 중복 계산된다는 점이다. 해결하려고 노력했지만 해결하지 못했고, 다른 사람의 풀이를 찾아봐 보았다. 

 

이 사람은 길이에 따라 최소 몇번 바꿔야하는지를 작성해 뒀는데, 여기서 규칙성을 찾을 수 있었다. 0 -> 1, 1 -> 0 이렇게 바뀔 때만 count를 1씩 증가시켜준다. count는 변화한 횟수를 담고 있기에 2로 나눠주면 된다.

 

(count + 1) // 2 와 같이 1을 더해준 이유는, 1을 더하고 몫만 가져오면 뒤집어야 할 횟수가 나오기 때문이다.

 

0과 1 -> 0번, 길이 1

01 -> 1번, 길이 2

010 -> 1번, 길이3

0101 -> 2번, 길이4

01010 -> 2번, 길이5

 

n = input()

cnt = 0

for i in range(len(n)-1): # i+1인덱스까지 비교하기 때문에 len(n) - 1로 범위를 지정해줘야 한다.
  if n[i] != n[i+1]:
    cnt +=1

print((cnt+1) // 2)

 

이번 문제를 풀면서 느낀점은 그리디는 아이디어를 떠올리고 그걸 바로 실행으로 옮기는게 쉽지만, 여기서 조금만 더 생각하는 것이 아직 부족한거 같다. 이 부분만 늘리면 그리디를 푸는데는 지장이 없을거 같다.