만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

홀짝 게임

면접 대비

시간 제한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