홀수 짝수의 묶음

문제 개요

주어진 수들을 사용해 각 묶음의 합이 다음 규칙을 만족하도록 여러 개의 묶음을 만들고자 한다:

• 첫 번째 묶음의 합은 짝수
• 두 번째 묶음의 합은 홀수
• 세 번째 묶음의 합은 짝수
• 네 번째 묶음의 합은 홀수
  ...

즉, 짝수 → 홀수 → 짝수 → 홀수 ... 형태로 번갈아가며 묶음을 만들어야 하며, 주어진 수를 전부 사용하여 만들 수 있는 최대 묶음 수를 구해야 한다.

핵심 아이디어

• 수의 값은 중요하지 않고 짝수/홀수 여부만 중요하다.
• 짝수 합 그룹은 짝수 1개 또는 홀수 2개로 만들 수 있다.
• 홀수 합 그룹은 홀수 1개로만 만들 수 있다.
• 각 단계에서 최소한의 수로 그룹을 만드는 것이 유리하다.
• 그룹 수가 늘어나지 못하는 경우, 마지막 그룹을 하나 줄이는 방식으로 처리한다.

구현 요약

1. 입력받은 수들을 짝수/홀수 개수로 나눈다.
2. groupNum을 0부터 시작하여,
   • 짝수 그룹 차례면 → 짝수 1개 또는 홀수 2개로 만든다.
   • 홀수 그룹 차례면 → 홀수 1개로 만든다.
3. 더 이상 그룹을 만들 수 없을 경우,
   • 홀짝 조건을 만족하지 못하면 마지막 그룹을 하나 줄여서 마무리한다.

시간복잡도

• O(N): 입력을 순회하며 짝수/홀수를 카운팅하고, 그룹 생성 시에도 상수 시간 연산만 수행.

정답 코드 (Java)

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++;
        }

        int groupNum = 0;
        while(true) {
            if(groupNum % 2 == 0) {
                if(even > 0) {
                    even--;
                    groupNum++;
                }
                else if(odd >= 2) {
                    odd -= 2;
                    groupNum++;
                }
                else {
                    if(even > 0 || odd > 0)
                        groupNum--;
                    break;
                }
            }
            else {
                if(odd > 0) {
                    odd--;
                    groupNum++;
                }
                else {
                    break;
                }
            }
        }

        System.out.print(groupNum);
    }
}