시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB195503929.104%

문제

아티스트 이동호는 세계적인 락스타 락동호의 동생이다. 아티스트 이동호는 그림을 N*M크기의 도화지에 그린다. 이동호는 까다롭기 때문에, 도화지를 1*1크기의 작은 칸으로 쪼개서 그림을 그린다. 동호는 미리 1*1크기의 칸으로 선을 그려놓았다.

동호는 흑백을 진정한 예술이라고 생각하기 때문에, 검정색과 흰색으로만 색칠한다. 동호는 N*M개의 칸을 모두 어떤 색으로 칠할 것인지 미리 정해놓았고, 이제 동호는 자신이 개발한 신기한 붓으로 모든 칸을 칠하려고 한다.

동호의 붓은 오직 수평으로만 칠할 수 있고, 칠하는 범위는 그 수평선상에서만 무제한이다. 따라서 칠하는 범위는 정확하게 1*N(세로*가로)크기의 직사각형이 된다. 또, 정확하게 붓은 선에서 시작해서 선에서 끝난다. 이 붓은 한가지 제약이 더 있는데, 칠하기 전에는 색을 두 가지 색 중 마음대로 정할 수 있지만, 칠하는 도중에는 색을 바꿀 수 없다.

그림의 본질을 살리기 위해서 동호는 각 칸을 절대로 두 번 이상 칠하지 않는다.

예를 들어, 다음과 같은 그림은 6번 만에 칠할 수 있다.

BBBBBBBBBBBBBBB
WWWWWWWWWWWWWWW
WWWWWWWWWWWWWWW
WWWWWBBBBBWWWWW

1번째 줄, 2번째 줄, 3번째 줄을 모두 한 번 만에 칠하고, 4번째 줄은 총 3번 만에 칠할 수 있다.

동호의 그림을 시기하던 오세준은 동호의 붓을 총 K번 사용하면 부서지도록 조절해놨다.

동호는 오세준의 상식을 뛰어넘는 천재이기 때문에, 오세준이 K번 사용제한을 걸어놓은 것을 알았다. 동호는 어쩔 수 없이 현실과 타협을 하기로 결정하고, 자신이 이미 칠하려고 결정해 놓은 대로 칠하지만, 잘못 칠한 부분을 최소로 하려고 한다.

못 칠한 부분도 잘못 칠한 부분으로 친다.

그림의 크기와 K, 그리고, 동호가 원래 칠하려고 했던 그림의 정보가 주어질 때, 동호가 잘못 칠한 부분의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 그림의 세로 크기 N과 가로 크기 M과 동호의 사용 제한 K가 주어진다. N과 M은 50보다 작거나 같은 자연수이고, K는 3000보다 작거나 같은 음이 아닌 정수이다. 둘째 줄부터 N개의 줄에 각 줄의 그림 정보가 M개 주어진다. 그림 정보는 문제에 나와있는 대로 B와 W만 주어진다.

출력

첫째 줄에 정답을 출력한다.

예제 입력 1

4 15 4
BBBBBBBBBBBBBBB
WWWWWWWWWWWWWWW
WWWWWWWWWWWWWWW
WWWWWBBBBBWWWWW

예제 출력 1

5

예제 입력 2

4 15 6
BBBBBBBBBBBBBBB
WWWWWWWWWWWWWWW
WWWWWWWWWWWWWWW
WWWWWBBBBBWWWWW

예제 출력 2

0

예제 입력 3

4 15 0
BBBBBBBBBBBBBBB
WWWWWWWWWWWWWWW
WWWWWWWWWWWWWWW
WWWWWBBBBBWWWWW

예제 출력 3

60

예제 입력 4

1 1 1
B

예제 출력 4

0

예제 입력 5

6 30 100
BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW
BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW
BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW
BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW
BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW
BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW

예제 출력 5

40

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: YunGoon