[BOJ 25379] 피하자

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

25379번: 피하자

 

- 문제 요약

 

음이 아닌 정수로 이루어진 길이 N의 배열 A = [A1, A2, · · · , AN]가 있다.

( N <=1,000,000 / 0 <=Ai <=2*10^9(1 <=i <=N) )

배열 A에서 인접한 두 수를 교환하는 시행을 원하는 만큼 할 수 있다.

이때, 홀수와 짝수가 인접한 경우가 최대 1번 등장하도록 하는 시행의 최소 횟수를 구하여라.

단, 0 또한 짝수로 간주함에 유의하라.

 

예를 들어, 아래 그림과 같이 A = [4, 5, 1, 0]인 상황을 살펴보자.

이 경우, 마지막 두 원소를 교환하는 시행과 가운데 두 원소를 교환하는 시행을 차례로 수행하면 A가 [4, 0, 5, 1]이 되어 홀수와 짝수가 인접한 경우가 최대 1번 등장하도록 할 수 있다.

 

 

- 알고리즘 정리

 

문제에서 중요한건 배열 요소의 값이 아닌, 각 배열 요소의 홀짝 여부이므로 배열에는 0, 1만 넣어주겠습니다.

문제를 해결하려면 배열을 오름차순(내림차순도 되긴 하나 이게 편하니까)으로 정렬하면 됩니다.

 

이제 정렬하는 방법을 생각해봐야 하는데, 평범하게 배열 내의 모든 쌍을 확인하며 교환하면 시간초과가 발생합니다.

i < j이고, Ai > Aj일 때 Ai=1, Aj=0이 성립합니다.

그러므로 문제를 해결하려면 Aj가 0일 경우, 현 인덱스보다 앞에 있는 1의 개수를 세어주면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 1000001
typedef long long ll;
int n,arr[MAX];
ll result=1e18,cnt,w;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		arr[i]%=2;
	}
	for(int i=0;i<2;i++){
		cnt=0;
		w=0;
		for(int j=1;j<=n;j++){
			if(arr[j]==i){
				w+=1;
			}
			else{
				cnt+=w;
			}
		}
		result=min(result,cnt);
	}
	cout<<result;
}

코드 제출 결과