Boj 25379 c++ 피하자

그리디는 여전히 어렵다. 이번에도 결국 구글링을 하였다.

수많은 시도들...

 

 

 

입력으로 N개의 숫자가 배열의 형태로 주어질 때, 두 수의 자리를 바꾸어 홀수와 짝수가 인접한 횟수가 1회가 되도록 정렬할 때, 두 수를 교환하는 최소 횟수를 구하는 것이 문제이다.

 

문제 풀이의 핵심은 횟수를 구하는 최적의 방법을 생각하는 것과, 교환 횟수가 계산되는 매커니즘을 이해하는 것에 있었다.

 

짝수나 홀수를 한 끝으로 모는 횟수를 계산하는 방법은 다음과 같다.

만약 홀수를 한쪽으로 정렬한다고 생각하면 짝수가 이전에 등장한 횟수만큼 원래의 총 횟수에 누적해 더해주어야 한다.

*이유가 뭘까?

왼쪽을 기준으로 생각하면 하나의 홀수 이전에 등장한 짝수를 모두 오른쪽으로 빼내어주어야 좌-홀수 우-짝수의 형태가 되기 때문이다. 이는 짝수의 경우에도 마찬가지이다. 때문에, 두 경우중에서 더 최적인 것을 출력해주면 된다.

사진에서도 마찬가지로 짝홀짝홀의 형태로 입력이 주어진 경우를 홀수 정렬, 짝수 정렬 두가지로 생각해보자.

 

case1. 짝수 정렬: 짝수 등장. 그전에 홀수가 등장한 횟수를 더해준다.

1+2=3

case2. 홀수 정렬: 홀수 등장. 그전에 짝수가 등장한 횟수를 더해준다. 

1+1=2

3>2

정답: 2

 

#include<iostream>
#include<vector>
using namespace std;

int main(){

   int N, odd_cnt=0, even_cnt=0;
   long long ans1=0, ans2=0;

   cin>>N;

   vector<int>v(N);

   for(int i=0; i<N; i++){
    cin>>v[i];
   }
   for(int i=0; i<N; i++){
    if(v[i]%2==0){
        even_cnt++;
        ans1+=odd_cnt;//짝수정렬
    }
    else{
        odd_cnt++;
        ans2+=even_cnt;//홀수정렬
    }
   }
   long long res=(ans1>=ans2)?ans2:ans1;
   cout<<res;
}