코드
# n = 100만 -> nlogn으로는 애매, O(N) 이하로 해결해야함
# 문제 조건: 홀수와 짝수가 인접한 경우가 최대 1번 등장하도록하는 시행의 횟수
# 홀수-짝수 교체가 1번 있어야한다.
# -> 홀수는 홀수끼리 모으고 짝수는 짝수끼리 모은다.
# -> 이렇게하면 최대 1번 교체된다.
# 최소 시행 횟수는?
# 짝수를 어디 모을지, 홀수를 어디 모을지 정할 기준
n = int(input())
num = [*map(int, input().split())]
cnt_odd = 0
cnt_even = 0
left_odd = 0 # 왼쪽에 홀수를 모으는 경우
left_even = 0 # 왼쪽에 짝수를 모으는 경우
for i in num:
if i%2 == 1:
cnt_odd += 1
left_odd += cnt_even
else:
left_even += cnt_odd
cnt_even += 1
print(min(left_even, left_odd)) # 최소 찾기
설계는 좋았는데 구현력이 모자라 해결하지 못한 문제. 설계를 더 구체적으로 해야겠다는 생각이 들었다.
'백준' 카테고리의 다른 글
[백준] 9934번 완전 이진 트리 파이썬 코드 (0) | 2024.03.02 |
---|---|
[백준] 1991번 트리 순회 파이썬 코드 (0) | 2024.03.02 |
[백준] 19941번 햄버거 분배 파이썬 코드 (0) | 2024.02.27 |
[백준] 21756번 지우개 파이썬 코드 (0) | 2024.02.23 |
[백준] 28215번 대피소 파이썬 코드 (0) | 2024.02.22 |