[자바로 푸는 백준] 25379번: 피하자

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

25379번: 피하자

🔶 풀이

알고리즘은 정말 둘 중 하나다.

엄청 잘 풀리거나 끝까지 막히거나..😭

 

홀수와 짝수가 인접한 경우가 최대 1번 등장하도록 만들어라.

즉, 모든 짝수 혹은 홀수를 왼쪽 혹은 오른쪽으로 이동시켜라.

 

필자는 짝수를 선택해서 왼쪽 혹은 오른쪽 끝으로 이동시켰다.

i번째 정수가 짝수라고 가정했을 때, 왼쪽 끝으로 이동할 경우에는 i, 오른쪽 끝으로 이동할 경우에는 N - 1 - i만큼 이동한다.

 

모든 정수를 탐색했다면 왼쪽 끝으로 이동했을 경우와 오른쪽 끝으로 이동했을 경우를 비교해서 작은 값을 선택하면 된다.

 

어느쪽으로 이동시켰을 때 더 적게 움직이는지까지 파악했다.

이제 교환을 몇 번 했는지를 찾아야된다.

 

처음에 모든 짝수를 왼쪽 혹은 오른쪽 끝으로 이동시킨다고 했다.

왼쪽으로 이동했을 경우 값이 더 작다고 가정했을 때, 모든 짝수는 왼쪽 끝에 있을 것이다.

최종적으로 숫자들을 왼쪽부터 순차적으로 배치해주면 된다.

 

[1] 

0

2

4

 

[2]

2

4 0 

 

[3]

4 0 2

 

숫자의 순서는 상관없다. 4번이 인덱스 0번 자리로 가려면 0번, 0이 인덱스 1번자리로 가려면 1번, 2가 인덱스 2번자리로 가려면 2번이다. 최종적으로 3번의 불필요한 움직임이 있었음으로 빼줘야된다.

 

또한, N의 범위가 1,000,000으로 위에서 설명한 과정을 반복하다보면 Lcnt, Rcnt 값이 int형으로 초과하기 때문에 long형으로 선언해줘야한다.

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        int N = Integer.parseInt(br.readLine()); // 개수
		
        long Lcnt = 0;
        long Rcnt = 0;
        long sum = 0;
        int idx = 0;
		
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            int num = Integer.parseInt(st.nextToken());
			
            if (num % 2 == 0) {
                sum += idx++;
                Lcnt += i;
                Rcnt += N - 1 - i;
            }
        }
        
        System.out.println(Math.min(Lcnt, Rcnt) - sum);
    }
}