[백준] 28298 - 더 흔한 타일 색칠 문제 (C++)

문제

https://www.acmicpc.net/problem/28298

풀이

발상 자체는 떠올리기 쉬울 수 있으나, 주어진 배열을 $K \times K$ 크기로 쪼개어, 그 내부를 탐색하는 과정은 쉽지 않을 수 있습니다.

먼저 for (int r = 0; r < K; r++), for (int c = 0; c < K; c++) 반복문을 선언하여 $K \times K$ 크기로 쪼개어 탐색을 진행하였습니다.
이어서, 각 타일에서 가장 자주 등장하는 색상(알파벳)을 알기 위해 colors 벡터를 선언하고, d[i][j] - 'A'로 A는 0, B는 1, C는 2… 에 할당해 줍니다.

colors 벡터를 모두 완성하였다면, 이제 가장 자주 등장한 색상과 그 횟수를 구해야 합니다. distance 함수로 알파벳을, max_element 함수로 횟수를 구하고, 최종 출력값인 change 변수에 더해줍니다.
이때 cell_count를 빼야 하는데, 가장 자주 등장한 색상은 바꾸는 횟수에 포함되서는 안되기 때문입니다.

코드

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int N, M, K;
  cin >> N >> M >> K;
  
  vector<vector<char>> d(N, vector<char>(M));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      cin >> d[i][j];
    }
  }

  int change = 0;
  for (int r = 0; r < K; r++) {
    for (int c = 0; c < K; c++) {
      vector<int> colors(26);
      int cell_count = 0;
      for (int i = r; i < N; i += K) {
        for (int j = c; j < M; j += K) {
          colors[d[i][j] - 'A']++;
          cell_count++;
        }
      }
      
      char best_char = 'A' + distance(colors.begin(), max_element(colors.begin(), colors.end()));
      change += cell_count - *max_element(colors.begin(), colors.end());
      
      for (int i = r; i < N; i += K) {
        for (int j = c; j < M; j += K) {
          d[i][j] = best_char;
        }
      }
    }
  }
  
  cout << change << "\n";
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
      cout << d[i][j];
    }
    cout << "\n";
  }
    
  return 0;
}