[백준] 25379번 피하자 파이썬 코드

코드

# 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)) # 최소 찾기

설계는 좋았는데 구현력이 모자라 해결하지 못한 문제. 설계를 더 구체적으로 해야겠다는 생각이 들었다.