README.md

[Silver III] 더 흔한 타일 색칠 문제 - 28298

문제 링크

성능 요약

메모리: 32436 KB, 시간: 636 ms

분류

브루트포스 알고리즘, 그리디 알고리즘, 구현

제출 일자

2024년 7월 12일 19:03:21

문제 설명

 N×M$N\times M$ 크기의 타일이 있다. 타일의 i$i$행 j$j$열에 해당하는 칸은 처음에 di,j$d_{i,j}$ 색으로 색칠되어 있다. 타일의 색상은 하나의 알파벳 대문자로 표현된다.

주어진 타일을 K×K$K\times K$ 크기의 작은 타일들로 겹치지 않게 나눴을 때, 나눠진 타일의 색상 배치가 전부 동일하도록 타일의 일부 칸을 골라 다시 색칠하고자 한다. 어떤 칸을 다시 색칠하는 데 사용할 수 있는 색상의 종류 또한 하나의 알파벳 대문자로 표현할 수 있는 색상 중 하나여야 한다.

최소 몇 개의 칸을 다시 색칠해야 하는지를 구하고, 이를 만족하는 타일의 색상 배치를 아무거나 하나 출력하라.

입력

첫째 줄에 세 정수 N$N$, M$M$, K$K$가 공백으로 구분되어 주어진다. (1≤N,M,K≤500;$(1\le N,M,K\le 500;$ N,M$N,M$은 K$K$의 배수이다)$)$ 

다음 N$N$개의 줄에는 타일의 i$i$행 색상 배치를 의미하는 길이 M$M$의 문자열 di$d_i$가 주어진다. di$d_i$는 알파벳 대문자로만 이루어져 있다.

출력

첫째 줄에는 다시 칠해야 하는 타일의 최소 개수를 출력한다.

다음 N$N$개의 줄에는 새로 칠한 타일의 i$i$행 색상 배치를 의미하는 길이 M$M$의 문자열을 출력한다. 출력하는 문자열 역시 모두 알파벳 대문자로만 이루어져 있어야 한다.