-
[Python] 1439 뒤집기Algorithm/백준 2023. 1. 31. 10:15
1. 문제 📚
https://www.acmicpc.net/problem/1439
2. 입출력 예 📋
3. 알고리즘 ✅
최소 횟수를 구하기 위해선 가장 적은 뭉텅이를 뒤집어야한다 → 그리디
예를 들어 0001100 이면 뭉텅이로 자르게 되면 0은 2개고 1은 1개이므로 1만 뒤집으면 최소행동이 될 것이다
따라서, 1. 뭉텅이로 잘라주고 (0, 1, 0)
2. 그 갯수를 세어 가장 작은 것을 프린트해주면 된다
4. 소스코드 💻
import sys N = list(sys.stdin.readline().strip()) # 뭉텅이로 잘라줌 stack = [N[0]] for i in range(1, len(N)): if N[i - 1] != N[i]: stack.append(N[i]) zero_count = stack.count('0') one_count = stack.count('1') print(min(zero_count, one_count))
'Algorithm > 백준' 카테고리의 다른 글
[Python] 2457 공주님의 정원 (0) 2023.02.03 [Python] 2847 게임을 만든 동준이 (0) 2023.01.31 [Python] 11053 가장 긴 증가하는 부분 수열 (0) 2023.01.20 [Python] 15657 N과 M (8) (0) 2023.01.20 [Python] 1987 알파벳(dfs) (0) 2023.01.19