[ SWEA 1240 ] 단순 2진 암호코드 (C++)

SWExpertAcademy의 단순2진암호코드(1240 / D3) 문제이다.

[ 문제풀이 ]

1) 이 문제는 7개의 숫자에서, 0과 1의 비율을 찾아서 올바른 암호코드인지 아닌지 판단 후, 올바른 암호코드라면

   문제에서 제시한 출력값을 도출해야 하는 문제이다.

   7개의 숫자는 a : b  : c : d 의 비율로 1과 0이 존재하며, a와 c는 '0'을, 'b'와 'd'는 '1'이 차지하는 칸이다.

   또한 주어진 맵에서 암호코드가 없는 라인은 '0'으로만 이루어져 있다.

   지금부터 0과 1의 4개의 비율을 a : b : c : d 라고 이야기 하겠다.

   그럼 지금부터 암호코드가 존재하는 라인을 찾았다고 가정해보자. 이 때, 만약 앞에서부터(가장 왼쪽부터)

   숫자를 찾는다면, a : b : c : d 의 비율을 정확하게 찾아낼 수 있을까 ??

   무슨 말인지 모르겠다면 이런 예시를 한번 생각해보자.

   000000011110100000 으로 존재하는 라인이 있다고 가정해보자. 이 안에는 '3'의 코드가 숨어있다.

   그런데 앞에서 부터 탐색하게되면, '1' 4개와, '0' 1개, '1' 1개 라는 것으로 '3'이라는 것을 찾아낼 수 있다.

   문제 없이 찾아낼 수 있다. 즉, 문제에서는 0과 1의 비율이 a : b : c : d 로 주어졌지만, 사실상 b : c : d 의 비율만

   보더라도 주어진 암호코드를 알 수가 있다.

   그럼 뒤에서 부터 찾게되면 ?? 마찬가지로 똑같은 방법으로 찾아낼 수가 있다.

   'd'가 '1'이 차지하는 비율이 위치하는 곳이기 때문에 뒤에서 부터 탐색할 때는..

   '1'의 갯수 파악 , '0'의 갯수 파악, '1'의 갯수 파악을 하게 되면 d : c : b의 비율을 알 수 있게 된다.

   즉, 어떤 방법을 써도 암호코드를 찾는데에는 문제가 없다. 본인은 이 중에서 뒤에서부터 탐색하는 방법을 이용해 보았다.

  

2) 탐색하는 방법은 이렇다.

   1) 뒤에서 부터 탐색하면서 '1'이 나오는 시점을 찾는다.

   2) '1'이 나왔을 때, 이 '1'이 'b'의 비율에 속하는 '1'인지, 'd'의 비율에 속하는 '1'인지 구분해주기 위해서, 'c'의 

      비율을 이미 탐색했는지 체크해 주는 변수를 통해서 판단하다.

      즉 'c'(0) 의 비율에 속하는 '0'의 갯수를 아직 판단하지 않았다면, 지금 나오는 '1'은 'd'의 비율에 속하는 놈

      일 것이고 'c'의 비율에 속하는 '0'의 갯수를 판단하고 넘어왔다면, 지금 나오는 '1'은 'b'의 비율에 속하는 놈

      일 것이다.

   3) 그렇게 처음 '1'이 나온 시점부터 총 7개의 숫자를 모두 판단해준다.

   4) 판단 후, b : c : d 의 비율을 저장한다.

   이렇게 b : c : d 의 비율을 저장했다고 가정해보자. 그럼 이게 제대로된 암호코드인지 어떻게 알 수 있을까 ??

   본인은 이부분을 위해서 미리 세팅해주는 코드를 만들었다.

   바로 Code[5][5][5] 라는 int형 3차원배열인데, [5][5][5]에 들어가는 값은, b, c, d의 비율을 의미한다.

   즉, Code[2][1][1] = 0 , Code[2][2][1] = 1, Code[1][2][2] = 2, Code[1][3][2] = 4 이런식으로

   미리 세팅해주었다. 정확한 암호코드가 아닌 값들(ex) Code[3][2][4]) 같은 값들은 모두 -1로 세팅해 주었다.

   즉, 우리는 b : c : d 의 비율을 구했으니 Code[b][c][d]의 값이 -1인지 아닌지 판단 후, 제대로된 암호코드라면

   문제에서 구하라는 값을 그대로 식을 통해서 도출해 내면 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define S_MAX 50
#define G_MAX 100
using namespace std;
 
int Code[5][5][5];
int MAP[S_MAX][G_MAX];
int N, M, Answer, Line, Answer_Arr[8];
 
void Setting_Code()
{
    /* 암호코드에 대한 b : c : d 의 비율을 미리 세팅해주는 함수*/
    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;        // 일단 -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;
    for (int i = 0; i < 8; i++)
    {
        Answer_Arr[i] = 0;
    }
}
 
void Input()
{
    /* 입력받는 함수 
     * 입력과 동시에, 암호코드가 존재하는 라인 ('1'이 존재하는 라인) 을 찾는다.
     * 어차피, 암호코드가 존재하는 라인은 모두 같기 때문에 한번만 찾으면 된다.
    */
    bool Flag = false;
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            char C; cin >> C;
            MAP[i][j] = C - '0';
            if (MAP[i][j] == 1 && Flag == false)
            {
                Flag = true;
                Line = i;
            }
        }
    }
}
 
void Solution()
{
    /* 암호코드를 해독하는 함수. */
    int Ans_Idx = 7;
    for (int j = M - 1; j >= 0; )
    {
        bool One, Zero;
        int Part[3] = { 0, 0, 0 };
        /* Part[0] = b , Part[1] = c , Part[2] = d 의 비율값을 의미. */
        /* One = Part[1]을 계산했는지 안했는지 여부를 판단하는 변수.('1'이 나왔을 때 b인지 d인지 구분하기 위함) */
        /* Zero = Part[0]을 계산했는지 안했는지 여부를 판단하는 변수.
          (Part[0]까지 계산했다면 이미 b, c, d 값을 다 구했음을 의미)*/
        One = Zero = false;
 
        if (MAP[Line][j] == 1)                    // 1을 찾았으면
        {
            for (int k = j; k > j - 7; k--)        // 7칸을 탐색한다.
            {
                if (MAP[Line][k] == 1)
                {
                    if (One == false) Part[2]++;
                    else
                    {
                        Part[0]++;
                        Zero = true;
                    }                    
                }
                else
                {
                    One = true;
                    if (Zero == false) Part[1]++;
                    else break;
                }
            }
        }
        else
        {
            j--;
            continue;
        }
 
        if (Code[Part[0]][Part[1]][Part[2]] == -1)
        {
            Answer = 0;
            return;
        }
        else
        {
            Answer_Arr[Ans_Idx--] = Code[Part[0]][Part[1]][Part[2]];
            j = j - 7;
        }
    }
 
    if (((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]) % 10 == 0)
    {
        for (int i = 0; i < 8; i++) Answer = Answer + Answer_Arr[i];
    }
    else Answer = 0;
}
 
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;
}