카드 뒤집기
시간 제한5초메모리 제한128 MB
R행 16열의 카드 배열에서 앞면으로 시작한 카드들을 목표 상태로 만들기 위해 행 또는 열의 연속 구간을 뒤집는 최소 연산 횟수를 구하는 문제입니다.
문제
R개의 행과 16개의 열로 된 카드 배열이 있다. 모든 카드는 처음에 앞면이다. 각 칸에는 0 또는 1이 적혀 있다. 0이 적힌 카드는 앞면으로, 1이 적힌 카드는 뒷면으로 보이게 만드는 것이 목표다.
한 번의 연산으로 한 행에서 연속한 카드 몇 장을 고르거나, 한 열에서 연속한 카드 몇 장을 골라 모두 뒤집을 수 있다. 뒤집은 카드는 앞면과 뒷면이 서로 바뀐다.
목표 상태를 만들기 위해 필요한 연산 횟수의 최솟값을 구하라. 뒤집는 카드의 총 개수가 아니라 연산 횟수를 최소화해야 한다.
입력
첫째 줄에 행의 수 R (1 <= R <= 50)이 주어진다. 다음 R개의 줄에는 길이가 16인 문자열이 하나씩 주어진다. 각 문자는 0 또는 1이다. 0은 최종적으로 앞면이어야 하는 카드, 1은 최종적으로 뒷면이어야 하는 카드이다.
출력
목표 상태를 만들기 위한 뒤집기 연산 횟수의 최솟값을 출력한다.