홀짝 게임

면접 대비

시간 제한3초메모리 제한128 MB

요약
빨간 카드와 파란 카드를 짝지어 합이 짝수인 쌍의 수를 최소로 만들 때, 메리가 확실히 이기는 게임 수의 최솟값을 구한다.
난이도

보통10점 중 5점

유형
그리디, 수학, 조합론, 구현
정답자
아직 제출이 없습니다

문제

홀짝(Odd or Even)은 두 사람이 사소한 문제(예: “누가 이 문제를 풀 것인가”)를 정할 때 하는 놀이다. 한 가지 방식에서는 먼저 두 사람이 각각 ‘홀’ 또는 ‘짝’을 부른다. 그런 다음 셋을 세고, 셋에 맞춰 두 사람이 동시에 한 손을 내밀어 0개부터 5개까지의 손가락을 보인다. 두 사람이 낸 손가락 수의 합이 짝수이면 ‘짝’을 부른 사람이 이기고, 합이 홀수이면 ‘홀’을 부른 사람이 이긴다.

John과 Mary는 홀짝 놀이를 여러 판 했다. 모든 판에서 John이 ‘홀’을 부르므로 Mary는 항상 ‘짝’이었다. 두 사람은 나중에 결과를 확인하려고 매 판마다 자신이 낸 손가락 수를 작은 카드 한 장에 적었다. Mary는 파란 카드에, John은 빨간 카드에 적었다. 그런데 하루가 끝날 무렵 John이 카드 묶음을 떨어뜨렸다. 색깔별로 나눌 수는 있었지만, 같은 색 안에서는 순서가 뒤섞여 원래의 판별 짝이 사라졌다.

빨간 카드에 적힌 수들의 모음과 파란 카드에 적힌 수들의 모음이 주어질 때, Mary가 확실히 이겼다고 말할 수 있는 최소 승리 횟수를 구하는 프로그램을 작성하라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 진행한 판 수를 나타내는 정수 NN이 주어진다 (1≤N≤1001 \le N \le 100). 둘째 줄에는 Mary가 각 판에서 보인 손가락 수를 나타내는 NN개의 정수 XiX_i가 주어진다 (0≤Xi≤50 \le X_i \le 5). 셋째 줄에는 John이 각 판에서 보인 손가락 수를 나타내는 NN개의 정수 YiY_i가 주어진다 (0≤Yi≤50 \le Y_i \le 5). N=0N = 0인 줄은 입력의 끝을 뜻하며 처리하지 않는다.

출력

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 이는 Mary가 확실히 이긴 최소 판 수이다.

예제3

  1. 예제 1

    입력
    3
    1 0 4
    3 1 2
    9
    0 2 2 4 2 1 2 0 4
    1 2 3 4 5 0 1 2 3
    0
    
    예상 출력
    0
    3
    
  2. 예제 2

    입력
    1
    0
    0
    0
    
    예상 출력
    1
    
  3. 예제 3

    입력
    1
    1
    0
    0
    
    예상 출력
    0