[ SWEA 1242 ] 암호코드 스캔 (C++)

SWExpertAcademy의 암호코드 스캔(1242 / D5) 문제이다.

[ 문제풀이 ]

1) 1240번 문제인 '단순 2진 암호코드' 에서 조금 더 응용된 버전의 문제이다. 아직 '단순 2진 암호코드'를 풀지 않았다면

   먼저 풀어보고 오는 것을 권장한다. (이 글에서도 단순 2진 암호코드 문제와의 차이에 대해서 언급을 많이 합니다 !)

   [ 단순2진 암호코드 풀이 바로가기(Click) ]

   '단순 2진 암호코드' 와는 다른 점이 몇가지가 있다.

    1. 입력이 2진수가 아닌, 16진수로 주어진다.

    2. 한 테스트 케이스 당, 숨어 있는 암호코드가 1개가 아니라 여러개가 존재할 수 있다.

    3. 암호코드가 주어진 비율이 아닌 비율로 주어질 수 있다.

       예를 들어서 문제에서 제시한 암호코드 '9'는 3 : 1 : 1 : 2의 비율은 갖는데, 0과 1의 비율이 3 : 1 : 1 : 2이 아닌

       9 : 3 : 3 : 6 이런식으로 주어질 수도 있다.

    이런 차이점들이 있다. 위의 부분만 잘 처리해준다면 '단순 2진 암호코드'와 전체적인 로직은 비슷하다.

    위에서 말한 부분들을 처리하는 방법들을 알아보자.

    1. 입력이 2진수가 아닌 16진수이다.

    - 본인은 이 부분을 처리하기 위해서 애초에 맵의 크기를 2000 x 2000으로 만들어주었다. 왜 2000일까 ??

      먼저 세로의 길이인 N은 최댓값이 2000이다. 그런데 가로의 길이인 M은 최댓값이 500이라고 했는데,

      왜 2000으로 잡았을까 ? 바로 16진수를 2진수로 변환하기 위함이다. 16진수에서 가장 큰 수인 'F'(15)를

      2진수로 바꾸면 어떻게 될까? '1111' 로 표현할 수 있다. 즉, 16진수 값 하나를, 2진수로 변경하기 위해서는

      총 4개의 비트가 필요하다. 그래서 본인은 이 부분 때문에 500 x 4 를 한 값인 2000으로 잡아주었다.

      그리고 또 한가지는 미리 16진수를 2진수로 편하게 바꾸기 위해서 배열을 하나 만들어주었다.

      바로 HexaToBinary[16][4] 라는 배열인데, HexaToBinary[a]의 의미는 다음과 같다.

      "a라는 16진수 값을 2진수로 나타내면 이렇게 4비트로 나타낼 수 있어요" 를 의미한다.

      간단한 예시를 몇개만 들자면, HexaToBinary[0] = { 0, 0, 0, 0 } 이 된다.

      HexaToBinary[4] = { 0, 1, 0, 0 } , HexatToBinary[10] = { 1. 0, 1, 0 } 이런식으로 미리 세팅해주었다.

      그리고 입력과 동시에 맵을 위에서 만들어준 방법을 통해서 2진수로 바꾸면서 맵에 넣어주었다.

      코드는 다음과 같다.

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < M; j++)
    {
        char C; cin >> C;        // char형 값 하나를 입력받는다.
        if (C <= '9') C = C - '0';  // 일단, 주어진 char형 값을 int형으로 변환
        else C = C - 'A' + 10;

        for (int k = 0; k < 4; k++) // 16진수 값 하나는 4개의 비트를 가지므로...
        {
            MAP[i][j * 4 + k] = HexaToBinary[C][k];   

           // 현재 자리에서 4칸을 차지한 칸을 2진수 비트로 변환해서 맵에 저장
        }
    }
}  

 

    2.한 테스트 케이스 당, 암호코드가 1개가 아닌 여러개가 주어질 수 있다.

    - 이 부분은, 나중에 암호코드를 찾기 위해 탐색할 때 '단순 2진 암호코드'와 달리 맵을 0행부터 N - 1 행까지

      모두 탐색해 봐야한다는 것을 의미한다.

   3. 암호코드가 주어진 비율이 아닌, 비율로 주어질 수도 있다.

    - 만약 3 : 2 : 1 : 2 라는 비율을 가진 암호코드가 있는데, 이게 6 : 4 : 2 : 4 로 숨어있다면 어떻게 3 : 2 : 1 : 2 로

      바꿀 수 있을까 ?? 뭔가 2로 나누면 될 것 같다는 생각이 든다.

      그럼 저 값이 9 : 6 : 3 : 6 으로 주어진다면 ? 뭔가 3으로 나누면 될 것 같다....

      즉, 우리는 비율을 알아냈을 때, 가장 작은 값으로 나눠주면 주어진 비율을 찾을 수 있다.

      따라서, 비율을 찾은 후에, 가장 작은 값으로 비율을 나눠주는 과정이 필요하다.

     

   위의 과정에 대한 처리만 해주면, 나머지는 단순2진 암호코드에서 했던 풀이와 동일하다.

   물론, 코드상으로는 조금 다를 수 있지만(조금 더 간략해 졌습니다) 로직은 동일하다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 2000
using namespace std;
 
int HexaToBinary[16][4] = {
    { 0, 0, 0, 0 }, // 0
    { 0, 0, 0, 1 }, // 1
    { 0, 0, 1, 0 }, // 2
    { 0, 0, 1, 1 }, // 3
    { 0, 1, 0, 0 }, // 4
    { 0, 1, 0, 1 }, // 5
    { 0, 1, 1, 0 }, // 6
    { 0, 1, 1, 1 }, // 7
    { 1, 0, 0, 0 }, // 8
    { 1, 0, 0, 1 }, // 9
    { 1, 0, 1, 0 }, // A
    { 1, 0, 1, 1 }, // B
    { 1, 1, 0, 0 }, // C
    { 1, 1, 0, 1 }, // D
    { 1, 1, 1, 0 }, // E
    { 1, 1, 1, 1 }  // F
};
 
int Code[5][5][5];
int Answer;
int N, M, Line;
int MAP[MAX][MAX];
 
void Setting_Code()
{
    for (int i = 0; i < 5; i++)
    {
        for (int j = 0; j < 5; j++)
        {
            for (int k = 0; k < 5; k++)
            {
                Code[i][j][k] = -1;
            }
        }
    }
    Code[2][1][1] = 0;
    Code[2][2][1] = 1;
    Code[1][2][2] = 2;
    Code[4][1][1] = 3;
    Code[1][3][2] = 4;
    Code[2][3][1] = 5;
    Code[1][1][4] = 6;
    Code[3][1][2] = 7;
    Code[2][1][3] = 8;
    Code[1][1][2] = 9;
}
 
void Initialize()
{
    Answer = 0;
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            char C; cin >> C;
            if (C <= '9') C = C - '0';
            else C = C - 'A' + 10;
 
            for (int k = 0; k < 4; k++)
            {
                MAP[i][j * 4 + k] = HexaToBinary[C][k];
            }
        }
    }
}
 
void Solution()
{
    int Answer_Idx = 7;
    int Answer_Arr[8] = { 0, };
 
    for (int i = 1; i < N; i++)
    {
        for (int j = M * 4 - 1; j >= 0; j--)
        {
            int Part[3] = { 0, 0, 0 };
 
            if (MAP[i][j] == 1 && MAP[i - 1][j] == 0)
            {
                while (MAP[i][j] == 1) { Part[2]++; j--; }
                while (MAP[i][j] == 0) { Part[1]++; j--; }
                while (MAP[i][j] == 1) { Part[0]++; j--; }
                j++;
 
                int Min = Part[2];
                if (Part[1] < Min) Min = Part[1];
                if (Part[0] < Min) Min = Part[0];
 
                for (int i = 0; i < 3; i++) { Part[i] = Part[i] / Min; }
                
                Answer_Arr[Answer_Idx--] = Code[Part[0]][Part[1]][Part[2]];
                
                if (Answer_Arr[Answer_Idx + 1] == -1)
                {
                    Answer = 0;
                    return;
                }
 
                if (Answer_Idx == -1)
                {
                    int Value = (Answer_Arr[0] + Answer_Arr[2] + Answer_Arr[4] + Answer_Arr[6]) * 3 + Answer_Arr[1] + Answer_Arr[3] + Answer_Arr[5] + Answer_Arr[7];
                    if (Value % 10 == 0)
                    {
                        for (int i = 0; i < 8; i++) Answer = Answer + Answer_Arr[i];
                    }
                    Answer_Idx = 7;
                }
            }
        }
    }
}
 
void Solve()
{
    Setting_Code();
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}