[1일 1알고] S3 3100 국기 인식

 

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

 

6*9크기의 배열을 삼등분된 국기로 만드는 문제입니다.

 

가로 세로를 나눠서 계산해야하나, 그런데 중간은 달라야하니 어떻게 계산해야하나 여러 고민을 했었는데

 

실제로는 배열의 크기가 6*9이고 가능한 색(알파벳)의 종류가 등분에 따라 중복을 포함해도 26*26*26이기 때문에 얼마 되지 않스빈다.

 

결론적으로 브루트 포스로 푸는 것이 가장 간단한 풀이였네요

 

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<string> v(6);
    for (int i = 0; i < 6; ++i)
        cin >> v[i];

    int result = 1e9;

    for (char a = 'A'; a <= 'Z'; ++a)
    {
        for (char b = 'A'; b <= 'Z'; ++b)
        {
            for (char c = 'A'; c <= 'Z'; ++c)
            {
                if (b == a || b == c)
                    continue;

                // 가로
                int cost1 = 0;
                for (int i = 0; i < 2; ++i)
                    for (int j = 0; j < 9; ++j)
                        if (v[i][j] != a)
                            ++cost1;

                for (int i = 2; i < 4; ++i)
                    for (int j = 0; j < 9; ++j)
                        if (v[i][j] != b)
                            ++cost1;

                for (int i = 4; i < 6; ++i)
                    for (int j = 0; j < 9; ++j)
                        if (v[i][j] != c)
                            ++cost1;

                result = min(result, cost1);

                // 세로
                int cost2 = 0;
                for (int i = 0; i < 6; ++i)
                {
                    for (int j = 0; j < 3; ++j)
                        if (v[i][j] != a)
                            ++cost2;

                    for (int j = 3; j < 6; ++j)
                        if (v[i][j] != b)
                            ++cost2;

                    for (int j = 6; j < 9; ++j)
                        if (v[i][j] != c)
                            ++cost2;
                }

                result = min(result, cost2);
            }
        }
    }

    cout << result;
    return 0;
}