[ SWEA 7673 ] 영이는 영이 시져시져! (C++)

SWExpertAcademy의 영이는 영이 시져시져!(7673 / D5) 문제이다.

[ 문제풀이 ]

주어진 맵에서 가장 왼쪽 위(1, 1)에서 가장 오른쪽 아래인 (N, N)까지 갈 때, 그 경로에 놓여진 숫자들을 모두 곱했을 때, 맨 뒷자리에 연속으로 있는 0의 갯수를 최소화 시켜야 하는 문제이다.

먼저 문제를 풀기 전에, 문제를 푸는데 핵심적인 역할을 할만한 중요한 사실을 하나 체크하고 시작해보자.

우리는 경로에 있는 숫자들을 "곱해서, 가장 뒤에 있는 0의 갯수를 최소화" 시켜야 한다.

그럼 ! 곱한 결과값의 가장 마지막에 숫자가 0을 만들 수 있는 숫자들은 뭐가 있을까 ??

간단하게 몇가지 예를 들어보자.

"2 x 3 x 7" 0이 있을까 ?? 곱하면 가장 뒤에 0이 나오질 않는다.

"4 x 5" 0이 있을까 ?? 4 x 5 = 20 으로 0이 나오게 된다. 우리는 0의 갯수를 최소화 시켜야 하기 때문에, 0의 갯수까지 파악해보자. 4 x 5 = 20 으로 0이 1개 발생하게 된다.

"3 x 4 x 25" ?? 3 x 4 x 25 = 300으로 0이 2개가 발생하게 된다.

그럼 ! 위의 식들을 통해서, 언제 0이 발생하지 않는지, 언제 발생하는지, 발생한다면 어떤 숫자들의 곱들로 이루어졌을 때 0이 발생하는지를 한번 체크해보자.

간단하게 생각하면, 숫자들끼리 곱했을 때, 그 숫자의 가장 마지막에 0이 온다 ? 라는 것은 그 숫자는 "10의 배수입니다." 를 의미한다. 10의 배수가 되기 위해서는, '10' 이라는 숫자에 어떤 숫자를 곱하든 무조건 가장 마지막에 0이 발생하게 된다.

그런데 ! 위에서 했던 식들을 다시한번 살펴보자.

Case1 : 2 x 3 x 7

Case2 : 4 x 5

Case3 : 3 x 4 x 25

위의 3가지 경우 모두, 그 어디에도 '10'을 곱했던 적은 없다. 즉 ! 10이라는 숫자가 없어도, 뒤에 0이 발생할 수 있다.

왜냐하면, 10은 또 다른 숫자들의 곱으로 만들 수 있는 숫자이기 떄문이다. (어렵게 생각하지 마세요. 너무나도 간단한 내용입니다.) 숫자 10은 '2'와 '5'의 곱을 통해서 만들 수가 있다. 즉 ! 대놓고 10을 곱하지 않더라도, 2와 5의 갯수만으로도 0의 갯수를 어느정도 예측할 수 있다는 것이다. 다시 말해서, "주어진 숫자를 소인수 분해 하였을 때, 2와 5의 갯수를 통해서 0의 갯수를 파악" 해보자는 것이다.

Case1을 살펴보자. 2 x 3 x 7 이다. 각각의 숫자들을 소인수분해 해보면, 2 x 3 x 7 그대로이다.

우리가 관심있는 숫자는 '2'와 '5'이다. 2가 1개 5가 0개가 있다. 그럼 발생할 수 있는 0의 갯수는 ?? 0개이다.

왜 ? 2와 5가 한 쌍으로 존재할 때, 0이 발생하게 된다. 즉 ! 2의 갯수와, 5의 갯수 중 더 작은 갯수만큼 0이 발생하게 된다.

Case2를 살펴보자. 4 x 5 이다. 이를 소인수분해 해보면, 2 x 2 x 5 가 되고, 2의 갯수는 2개, 5의 갯수는 1개가 된다.

그럼, '2' 1개와, '5'1개를 한 쌍으로 묶어서 10을 만들게 되면, '2'가 하나 남게 된다. 즉, 0이 1개가 발생하게 되는 것이다.

위에서 했던 대로, 2의 갯수와 5의 갯수를 비교해서 더 작은 갯수만큼 0이 발생하게 되므로 이에 대입해서 풀어보면

2는 2개, 5는 1개 이므로 더 작은 갯수는 1개가 되고, 0이 1개가 발생하게 되는 것이다.

Case3을 살펴보자. 3 x 4 x 25인데 이를 소인수 분해 해보면, 3 x 2 x 2 x 5 x 5 가 된다.

2가 2개가 있고, 5가 2개가 있다. 더 작은 갯수는 2개가 되므로, 0이 총 2개만큼 발생한다는 것이다.

실제로 계산해보면 3 x 4 x 25 = 300 으로 0이 가장 마지막에 2개가 발생하게 된다.

이 원리를 이용해서 문제를 해결해볼 것이다.

따라서, 본인은 문제를 풀기전에, 주어진 맵에 있는 모든 숫자들을 소인수 분해해서, 2의 갯수와 5의 갯수를 미리 계산해 주었다. 움직일 때는 , 무조건 아래쪽 혹은 오른쪽으로만 움직일 수 있다고 했다. 그럼 현재 좌표에서 오른쪽 혹은 아래쪽으로 움직이는 형태이니, 움직여지는 그 다음 좌표의 입장에서는 "위쪽 혹은 왼쪽에서 오는 경우" 2가지가 발생한다.

그럼 ? 우리는, 위쪽에서 왔을 때, 2와 5의 갯수와 왼쪽에서 왔을 때, 2와 5의 갯수를 비교해서 더 최소의 갯수인 경로를 선택해서 진행할 수 있다.

하지만 ! 맵에서 "가장 윗줄" 과, "가장 왼쪽줄" 입장에서는 선택권이 없어지게 된다. 왜냐하면, 가장 윗줄에 입장에서 본다면, 그보다 더 위에서 내려오는 경로가 존재할 수 없기 때문이다. 따라서, 무조건 왼쪽에서 오는 경로로만 계산을 해주어야 한다.

또한, 가장 왼쪽줄 입장에서 보면 더 왼쪽에서 오는 경로는 없기 때문에, 무조건 위쪽에서 내려오는 경로로만 계산을 해 주어야 한다. 그게 아닌 좌표들의 입장에서는 ??

비교를 할 수가 있다. 왼쪽에서 왔을 때, 2의 갯수와 5의 갯수, 위쪽에서 내려왔을 때, 2의 갯수와 5의 갯수를 계산해서 더 적은 2와 5를 가지고 있는 경로를 선택하게 되는 것이다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N, Answer;
int MAP[MAX][MAX];
int Two[MAX][MAX];
int Five[MAX][MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Initialize()
{
    Answer = 0;
}
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Calculate_MAP()
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (MAP[i][j] == 0)
            {
                Two[i][j] = 2e9;
                Five[i][j] = 2e9;
                continue;
            }
 
            int Value = MAP[i][j];
            int Two_Cnt = 0;
            int Five_Cnt = 0;
 
            while (Value % 2 == 0)
            {
                Two_Cnt++;
                Value = Value / 2;
            }
            while (Value % 5 == 0)
            {
                Five_Cnt++;
                Value = Value / 5;
            }
            Two[i][j] = Two_Cnt;
            Five[i][j] = Five_Cnt;
        }
    }
}
 
void Solution()
{
    Calculate_MAP();
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (MAP[i][j] == 0) continue;
            if (i == 1 && j == 1) continue;
 
            if (i == 1)
            {
                Two[i][j] = Two[i][j] + Two[i][j - 1];
                Five[i][j] = Five[i][j] + Five[i][j - 1];
                continue;
            }
            if (j == 1)
            {
                Two[i][j] = Two[i][j] + Two[i - 1][j];
                Five[i][j] = Five[i][j] + Five[i - 1][j];
                continue;
            }
 
            int Left_Cnt = Min(Two[i][j] + Two[i][j - 1], Five[i][j] + Five[i][j - 1]);
            int Up_Cnt = Min(Two[i][j] + Two[i - 1][j], Five[i][j] + Five[i - 1][j]);
            
            if (Left_Cnt < Up_Cnt)
            {
                Two[i][j] = Two[i][j] + Two[i][j - 1];
                Five[i][j] = Five[i][j] + Five[i][j - 1];
            }
            else
            {
                Two[i][j] = Two[i][j] + Two[i - 1][j];
                Five[i][j] = Five[i][j] + Five[i - 1][j];
            }
        }
    }
    Answer = Min(Two[N][N], Five[N][N]);
}
 
void Solve()
{
    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;
}