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

문제링크 : https://www.acmicpc.net/problem/28298

28298번: 더 흔한 타일 색칠 문제

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

char tile[501][501];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    int N, M, K, sum = 0;
    cin >> N >> M >> K;
    string s;

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            cin >> tile[i][j];
        }
    }

    for(int i=0; i<K; i++)
    {
        for(int j=0; j<K; j++)
        {
            vector<int> alpha(26);
            for(int k=i; k<=N; k+=K)
            {
                for(int l=j; l<=M; l+=K)
                {
                    alpha[tile[k][l]-'A']++; //알파벳 갯수 카운트
                }
            }
            int maxV = *max_element(alpha.begin(), alpha.end()); //각 구역별 가장 많은 문자수
            int idx = max_element(alpha.begin(), alpha.end()) - alpha.begin(); //가장 많은 문자수의 위치

            sum += ((N*M)/(K*K) - maxV); //변환해야 하는 수 더해주기

            for(int k=i; k<=N; k+=K)
            {
                for(int l=j; l<=M; l+=K)
                {
                    tile[k][l] = idx + 'A'; //가장 많은 문자로 갱신
                }
            }
        }
    }

    cout << sum << "\n";
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<M; j++)
        {
            cout << tile[i][j];
        }
        cout <<'\n';
    }

    return 0;
}

타일의 각 영역을 확인하여 가장 많은 문자수를 구하고 다른 문자들을 가장 많은 문자수로 변환해주는 문제다.

이렇게 변환이 일어나는 갯수는 해당 영역 전체 타일의 갯수에서 변하지 않은 (가장 많은 문자수의 갯수를 제외한) 갯수를 구해주면 된다.

 

여기서 가장 많은 문자수의 위치를 구하는 것에 조금 헤맸는데, 처음에는 그냥 반복문으로 최대값을 구하고 이때 인덱스를 따로 저장했다.

그런데 다른 사람의 코드와 검색을 통해 찾아보니 배열이 아닌 벡터의 경우 max_element를 이용하여 가장 많은 문자수의 위치를 찾을 수 있다는 것을 알고 기존에 배열로 선언하고 memset을 통해 초기화시켜줬던 것을 바로 벡터를 선언해줬다.

 

탐색 방식은 다음과 같다.

<예제>
ABCBAB
BBACCA
BPAZBB
BBAABB

K = 2

AB CB AB
BB AC CA
BP AZ BB
BB AA BB

K씩 우로 이동 첫 탐색 A, C, A
K씩 아래로 이동 이후 탐색 B, A, B
가장 많은 문자수 A, 나머지를 A로 바꿔줌

다음 탐색
B, B, B
P, Z, B
가장 많은 문자수 B, 나머지를 B로 바꿔줌

이하 반복

구역이
AB
BB
이면 A의 위치 -> B의 위치 -> B(하단)의 위치 -> B의 위치 순으로 탐색하는 것