시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 488 | 327 | 286 | 69.082% |
2016년 국제정보올림피아드는 러시아에서 열린다.
러시아 국기는 3개의 색으로 구성되어 있다. 가장 윗 줄이 흰색, 다음 줄이 파란색, 마지막 줄이 빨간색으로 되어 있다.
JKJeong선생님께서 N*M 격자판을 들고 왔다. 이 격자판은 각 칸이 흰색, 파란색, 빨간색 중 하나의 색으로 칠해져 있다. 선생님께서는 이 격자판을 이용하여 러시아 국기를 만들라는 과제를 주셨다.
만드는 규칙은 다음과 같다.
위 규칙을 만족시키면서 러시아 국기형태로 만드는데 드는 최소 색칠 수를 구하는 프로그램을 작성하시오.
첫 번째 줄에 N, M이 공백으로 구분되어 입력된다. (3 ≦ N ≦ 50, 3 ≦ M ≦ 50)
다음 줄부터 N줄에 걸쳐서 M개씩의 문자열이 주어진다.
각 문자열은 대문자로 "W", "B", "R" 중 하나의 문자로 구성된다.
"W"는 흰색, "B"는 파란색, "R"은 빨간색을 의미한다.
러시아 국기 형태로 만들기 위해 색을 바꿔야할 최소 개수를 출력한다.
4 5 WRWRW BWRWB WRWRW RWBWR
11
6 14 WWWWWWWWWWWWWW WBBBWWRRWWBBBW WWBWWRRRRWWBWW BWBWWRRRRWWBWW WBBWWWRRWWBBBW WWWWWWWWWWWWWW
44
1번 예제는 다음과 같은 방법으로 두 입력 예제에서 러시아 국기를 만들 수 있다.
2번 예제는 이렇게 생겼다.