[자바] 백준 25379 - 피하자 (java)

 문제 : boj25379

---

 

필요 알고리즘 개념

• 그리디 알고리즘
  
  • 논리적으로 어떻게 하는게 항상 최선일지 잘 생각해 규칙을 잘 정해보면 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  그리디 문제이니, 내가 이 문제를 풀면서 생각한 흐름 그대로 풀이로 쓰는게 나을 것 같다.

 

1. 문제에서 요구하는 '홀수와 짝수가 인접한 경우가 최대 1번 등장하도록 하는 시행' 은 결국 '모든 짝수가 왼쪽이고 모든 홀수가 오른쪽' 이거나, '모든 짝수가 오른쪽이고 모든 홀수가 왼쪽'인 경우이다.

 

2. 그렇다면 경우의 수는 다음과 같다.

2.1 짝수가 왼쪽으로 가는 경우의 교환 횟수

2.2 짝수가 오른쪽으로 가는 경우의 교환 횟수

2.3 홀수가 왼쪽으로 가는 경우의 교환 횟수

2.4 홀수가 오른쪽으로 가는 경우의 교환 횟수

 

 

3. 근데 이 때, 2.1은 2.4와 동일하고, 2.2와 2.3은 동일하다. 즉, 4가지 경우의 수가 아니라 2가지 경우만 보면 된다. 짝수 혹은 홀수 하나만 정해서 그게 왼쪽에 붙는 경우의 수와 오른쪽에 붙는 경우의 수를 생각하면 된다. 내 경우엔 짝수로 정했다.

 

  짝수가 가장 왼쪽에 붙고자 하는 경우의 이동 횟수를 cntL, 가장 오른쪽에 붙고자 하는 경우의 이동 횟수를 cntR 이라 해보자. 입력으로 들어온 위치의 인덱스 번호를 i라 할 때, i번 위치의 짝수에 대해 cntL은 i만큼 증가하면 되고, cntR은 N-1-i 만큼 증가하면 될 것이다.

 

 

4. 그렇다면 고르고자 하는 경우는 cntL, cntR 중 작은 값이 된다. cntL이 작았다면, 짝수는 왼쪽에 붙이고 홀수는 우측에 붙이는 것이 더 이동횟수가 작았음을 뜻한다.

 

 

5. 그럼 이제 어떤 경우를 선택해야 하는지는 파악했고, 실제 이동 횟수는 어떻게 구할 수 있을까?

 

  사실 어떤 수가 어떤 위치에 와야 더 작은 이동횟수를 가지는지는 우리에게 중요한게 아니다. 즉, "2 4 5 6" 이 있다면, 우린 직관적으로 5와 6만 바꾸고 나머지 2와 4는 그대로 두는게 더 나은 방법이란걸 안다. 하지만 이걸 프로그램적으로 2와 4는 그대로 둬야하고, 6은 움직여야한다는걸 직접 찾아내는건 상당히 복잡한 일이다. 그리고 사실 그건 알 필요가 없다. 내가 작성한 생각의 흐름대로 풀 경우, "2 4 5 6"의 경우 cntL은 4, cntR은 5가 된다. 그러므로 짝수를 왼쪽에 붙이는게 이득이라는 것 까진 알 수 있다. 하지만 난 2,4는 그대로 둬야 한다는 것은 찾지 않았다.

 

  이 상태에서 실제 이동 횟수를 구하는데 중요한건 총 몇 개를 움직였냐이다. 내 경우엔 짝수만 보고 있으므로 즉, 짝수가 총 몇개였냐는 말과 동일하다. 총 3개의 짝수를 움직인게 되고 그걸 cntL이 4로 더 작으므로 좌측으로 붙이기로 했다. 그리고 cntL은 인덱스 0번에 전부 붙이는 경우를 가정해서 세둔 횟수이다. 그럼 실제론 인덱스 0번, 1번, 2번 위치에 배치하면 될 것이므로, 0번에서부터의 차이 0, 1, 2 번만큼 덜 움직여도 된다. 따라서 0+1+2 = 3이 되고, 실제 이동 횟수는 cntL - 3을 해서 1이 답이 된다. 무슨 말이냐면, 어쨌든 들어갈 위치만 파악 되었다면 최선을 다해 최소한의 횟수로 배치할 것임을 가정하고 수학적으로 답을 계산한 것이다. 그리고 그렇게 배치할 방법은 실제로 존재하지만 (위의 예시에서 6만 5와 교환하는 방법) 그걸 우리가 알 필요는 없다.

 

  아무튼 그러니 결론은 1~4를 통해 짝수를 좌측으로 붙이는게 나은지, 우측으로 붙이는게 나은지 구하고, 짝수의 갯수가 k개였을 경우 0부터 k-1까지의 등차수열 합을 min(cntL, cntR)에서 빼주면 답이 된다.

 

 

6. 추가로, N은 최대 100만이므로 모든 값이 짝수였다면 cntL은 0+1+...+(1000000-1) = 1000000 x (1000000-1) / 2가 된다. 즉 int형으로 표현 가능한 범위를 넘어가므로 long으로 계산해줘야 한다.

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long cntL = 0;
        long cntR = 0;
        long sum = 0;
        int idx = 0;
        for (int i = 0; i < n; i++) {
            int cur = Integer.parseInt(st.nextToken());
            if (cur%2 == 0) {
                sum+=idx++;
                cntL += i;
                cntR += n-1-i;
            }
        }
        System.out.println(Math.min(cntL, cntR) - sum);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}