[코드트리] 홀수 짝수의 묶음

간만에 봐도 잘 이해가안되는 문제가 생겨서 기록한다.. 그리고 기간이 얼마안남아서,, 흑흑 증말 어렵다

---

N개의 숫자들이 주어지면 주어진 숫자들을 전부 사용하여, 각 묶음으로 나눠 각각의 합을 구했을 때 첫 번째 묶음부터 순서대로 그 합이 짝수, 홀수, 짝수, 홀수, 짝수, … 이렇게 짝수에서 시작하여 짝홀이 계속 번갈아가면서 나오게끔 하는 만들 수 있는 최대 묶음 수를 구하는 프로그램을 작성해보세요. 단, 주어진 순서에 상관없이 묶음을 만들어도 됩니다.

 

입력 형식

첫 번째 줄에는 주어지는 숫자의 개수 N이 주어집니다.

두 번째 줄에는 N개의 숫자가 공백을 사이에 두고 주어집니다.

• 2 ≤ N ≤ 1,000
• 1 ≤ 주어지는 숫자들 ≤ 100

출력 형식

첫 번째 줄에 짝홀이 계속 번갈아가면서 나오게끔 하는 만들 수 있는 최대 묶음 수를 출력합니다.

 

입출력 예제

예제1

입력:

7
1 3 9 7 5 11 3

출력:

3

 

예제2

입력:

7
11 2 17 13 1 15 3

출력:

5

예제 설명

첫 번째 예제에서 1 3 9 7 5 11 3 이 주어졌습니다. 1 3 / 9 7 5 / 11 3 이렇게 묶음을 만들면 짝수, 홀수, 짝수가 되므로 조건을 만족하는 3개의 묶음을 만들 수 있게 됩니다. 1 3 / 9 / 7 5 / 11 이렇게 4개를 만들수도 있지만 원소 3이 하나 쓰이지 않고 남게 되기 때문에 이 방법은 사용할 수 없습니다.

 

---

Intuition

 

그룹의 숫자를 고를 때 어느 숫자를 고르던 그 숫자의 홀짝이 같다면 그룹의 총합에서 홀짝도 같아지게 됩니다. 따라서 어느 숫자를 골랐는지 알 필요가 없으며, 짝수와 홀수 중 어느 숫자를 새로 골랐는지만 정보를 가지고 있다면 문제를 풀 수 있습니다. 또한, 그룹을 나눌때는 숫자를 가능한 적게 사용해야 남은 숫자들로 더 많은 그룹을 만들 가능성이 생깁니다.

 

Algorithm

묶음이 짝수, 홀수 순서로 번갈아가며 나오게 해야 합니다.

• 짝수 묶음을 만들 때에는 짝수 숫자 1개로 그룹을 만드는 것이 최선이며, 만약 짝수 숫자가 부족하다면, 홀수 숫자 2개로 그룹을 만드는 것이 최선입니다.

• 홀수 묶음을 만들 때에는, 홀수 숫자 1개로 그룹을 만드는 것이 최선이며, 짝수 숫자만으로는 홀수 묶음을 만들 수 없습니다.

홀수만 존재하는 예제를 알아봅시다. 다음과 같은 7개의 홀수가 주어져있습니다.

예제에서는 홀수밖에 주어지지 않았으므로, odd의 값이 7이 되고 짝수그룹, 홀수그룹 순서로 묶습니다.

이렇게 묶다보면 마지막에 홀수 3이 남습니다. 다음과 같이 이 3을 묶기 위해 11과 같이 묶어보았지만, 짝수그룹 2개가 연속되어 있으므로 불가능한 상태가 됩니다.

이 상태를 해결하기 위해 짝수그룹 (7, 5)와 짝수그룹 (11, 3)를 하나로 묶어 해결합니다.

이렇게 총 3개의 그룹으로 묶어 해결할 수 있습니다.

이번엔 홀수와 짝수가 같이 존재하는 예제를 알아봅시다. 다음과 같은 6개의 짝수 또는 홀수가 주어져있습니다.

이번에는 짝수 4가 있으므로, 맨 처음에 짝수그룹에 4만 넣습니다.

그 후, 짝수와 홀수 순서대로 묶다보면 마지막에 홀수 3이 남습니다. 3을 묶기 위해 7과 같이 묶어보았지만, 짝수그룹 2개가 연속되어 있으므로 불가능한 상태가 됩니다.

이 상태를 해결하기 위해 짝수그룹 (9, 7)와 짝수그룹 (5, 3)를 하나로 묶어 해결합니다.

이렇게 총 3개의 그룹으로 묶어 해결할 수 있습니다.

 

코드

import java.util.Scanner;

public class Main {
    public static final int MAX_N = 1000;
    
    public static int n;
    public static int[] blocks = new int[MAX_N];
    public static int odd, even;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 입력:
        n = sc.nextInt();
        for(int i = 0; i < n; i++)
            blocks[i] = sc.nextInt();
        
        // 생각해 보면, 그룹의 숫자를 고를 때 어느 숫자를 고르던
        // 그 숫자의 홀짝이 같다면 그룹의 총합에서 홀짝도 같아지게 됩니다.
        // 따라서 어느 숫자를 골랐는지 알 필요가 없으며, 짝수와 홀수 중 어느 숫자를
        // 새로 골랐는지만 정보를 가지고 있다면 문제를 풀 수 있습니다.  
        for(int i = 0; i < n; i++) {
            if(blocks[i] % 2 == 0)
                even++;
            else
                odd++;
        }
        
        // 그룹을 나눌때 숫자를 가능한 적게 쓰는 것이 유리합니다. 숫자를 적게 사용해야
        // 남은 숫자들로 더 많은 그룹을 만들 가능성이 생기기 때문입니다.

        // 생각해보면, 홀수 그룹을 만들 때 짝수 숫자를 그룹에 넣는것은 의미가 없습니다.
        // 짝수 숫자를 넣으나 마나 어차피 그룹의 홀짝성이 변하지 않기 때문입니다.
        // 따라서 홀수 그룹을 만들 때에는 짝수 숫자를 넣지 않고 홀수 숫자만 1개로
        // 그룹을 형성하는 것이 유리합니다.
        // 짝수 그룹을 만들 때에는 홀수 2개로 만들거나 짝수 1개로 만들 수 있는데,
        // 홀수 그룹을 만들 때에 사용되지 않는 짝수 숫자부터 그룹에 이용하는 것이 유리합니다.

        int groupNum = 0;
        while(true) {
            // 묶음을 짝수, 홀수를 번갈아가며 나오게끔 해야 하므로
            // groupNum이 짝수일 때, 묶음은 짝수로 만들어야 하고
            // groupNum이 홀수일 때, 묶음은 홀수로 만들어야 합니다.

            if(groupNum % 2 == 0) {
                // 짝수 묶음을 만들 때에는, 짝수 숫자 1개로 그룹을 만드는 것이 최선입니다.
                // 만약 짝수 숫자가 부족하다면, 홀수 숫자 2개로 그룹을 만드는 것이 최선입니다.
                if(even > 0) {
                    even--;
                    groupNum++;
                }
                else if(odd >= 2) {
                    odd -= 2;
                    groupNum++;
                }
                else {
                    // 더 이상 그룹을 만들지 못하는 상황입니다.

                    // 아직 숫자가 남아있다면 남아 있는 숫자들로 짝수 그룹을 만들지 못합니다.
                    // 이 경우 ... + (짝수 그룹 A) + (홀수 그룹 B) + (나머지 C(홀수 그룹))
                    // 다음과 같은 상태인데, 무슨 짓을 해도 그룹의 개수를 늘리거나 유지해서는
                    // 문제 조건을 만족할 수 없습니다.

                    // 그 이유는 그룹의 개수를 늘리려면 ... + 짝수 그룹 + 홀수 그룹 + 짝수 그룹 형태가,
                    // 그룹의 개수를 유지하려면 ... + 짝수 그룹 + 홀수 그룹 형태가 되어야만 하는데
                    // 홀짝성을 생각해 보았을 때 이는 불가능합니다.
                    // 따라서 그룹의 개수를 1개 줄이는
                    // ... + 짝수 그룹(A + B + C) 형태가 최선입니다.
                    if(even > 0 || odd > 0)
                        groupNum--;

                    break;
                }
            }
            else {
                // 홀수 묶음을 만들 때에는, 홀수 숫자 1개로 그룹을 만드는 것이 최선입니다.
                // 짝수 숫자만으로는 홀수 묶음을 만들 수 없습니다.
                if(odd > 0) {
                    odd--;
                    groupNum++;
                }
                else {
                    // 더 이상 그룹을 만들지 못하는 상황입니다.

                    // 아직 숫자가 남아있다면 남아 있는 숫자들로 홀수 그룹을 만들지 못합니다.
                    // 이 경우 ... + (홀수 그룹 A) + (짝수 그룹 B) + (나머지 C(짝수 그룹))
                    // 다음과 같은 상태인데, 무슨 짓을 해도 그룹의 개수를 늘리는 방식으로는
                    // 문제 조건을 만족할 수 없습니다.

                    // 그 이유는 그룹의 개수를 늘리려면 ... + 홀수 그룹 + 짝수 그룹 + 홀수 그룹 형태가
                    // 되어야만 하는데 홀짝성을 생각해 보았을 때 이는 불가능합니다.
                    // 따라서 그룹의 개수를 유지하는
                    // ... + (홀수 그룹 A) + (짝수 그룹 (B + C)) 형태가 최선입니다.

                    break;
                }
            }
        }

        System.out.print(groupNum);
    }
}