7673. 영이는 영이 시져시져!

출처

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

 

DP 문제

-이유.

값을 누적 저장 불가. -> DFS나 BFS를 통해 누적된 값을 전달하는 방식을 쓰려고 해도 

한번의 곱에 최대 10^6씩 곱해지므로  1000번 곱해지면 받아줄 수 있는 자료형이 없다. (최대 10^6000.... ㅎㄷㄷ)

 

아이디어

1. 0을 만드는 경우를 분석한다 

-> 2와 5의 곱 한번으로 0이 하나 만들어진다. 만약 2개의 2와 3개의 5가 곱해진다면 0이 2개 만들어진다.

즉 어떤 곱에 이르렀을 때 , 그 수가 가지고 있는 2와 5의 거듭 제곱의 갯수 중에 최소값 만큼 0이 생성됨.

 

2. 그렇다면 2와 5를 줄이는 방식으로 가야 한다.

1) 2과 최소인 방향으로 접근

2) 5가 최소인 방향으로 접근

 

전체적인 틀은 좌표에 따라 입력되는 수의 2와 5의 개수를 각각의 배열에 저장한다.

그리고 2의 관점과 5의 관점으로 따로 생각해서 어떤 지점까지 이동하는데 2가 최소인 방향으로 이동한다면

해당 지점이 2를 몇개를 갖게 될지, 5에 대해서도 마찬가지의 방식으로 생각.

 

시작점 즉 0,0 에서 같은 행, 같은 열은 이동방향이 오른쪽과 아래 밖에 없으므로 자신의 이전 좌표를 무조건 거쳐서 와야한다. 따라서 현재 자신의 2혹은 5의 값에 이전좌표의 2,5의 값을 더 해 준값을 자신이 다시 가지면  해당 좌표까지 도달하는데 갖게되는 2와 5의 값이다.

이 때, 주의 할 점은 만약 자신의 전 좌표가 0의 값을 갖는 좌표라면 그 좌표를 피해서 올 수는 없으므로 자신또한 0과 같은 신세가 된다. 

 

테두리가 아닌 그 안에 있는 좌표는 i,j좌표라면 i-1,j 혹은 i,j-1을 최종으로 거쳐서 들어오게 되므로 i,j좌표와 

최종 좌표 중 최소의 값을 갖는 좌표의 합을 더 해 주면 된다.

이 때도 만약 두 최종좌표가 모두 -1의  개수를 갖는다면 자신에게 도달할 수 없다는 뜻이므로 자신도 -1의 값이 되어야 하고 둘중에 하나만 -1의 값이라면 나머지 하나로 이동해야 한다 .

무턱대고 min으로 비교해버리면 -1이 더 작은 값으로 선정되기 때문에 주의한다.

 

 

#include<iostream>
#include<queue>


using namespace std;


int arr[1000][1000];
int two[1000][1000];
int five[1000][1000];

long N;
long result;

int check2(int num)
{
	int temp_two = 0;
		
	while(!(num%2))
	{
			
		num = num /2;
		temp_two++;
			
	}
	
	return temp_two;
	
}

int check5(int num)
{
	int temp_five = 0;
		
	while(!(num%5))
	{
			
		num = num /5;
		temp_five++;
			
	}
	
	return temp_five;
	
	
}



int main(void)
{
	
	int test_case;
	cin >> test_case;
	
	
	for(int tc = 1; tc <= test_case; tc++)
	{
		

		cin >> N;
		result = 0;

		
	
		
		
		for(int i = 0; i < N; i++)
		{
			
			for(int j = 0; j < N; j++)
			{
				
				
				cin >> arr[i][j];
				if(arr[i][j] != 0)
				{
					two[i][j] = check2(arr[i][j]);
					five[i][j] = check5(arr[i][j]);
				}
				else
				{
					two[i][j] = -1;
					five[i][j] = -1;
					
				}
				
				
				
			}
		}
		
		for(int i = 1; i < N; i++)
		{
			
			if(two[0][i] != -1 && two[0][i-1] != -1)
			{
				two[0][i] += two[0][i-1];
			}
			else
			{
				two[0][i] = -1;
			}
			
			
			if(two[i][0] != -1 && two[i-1][0] != -1)
			{
				two[i][0] += two[i-1][0];
			}
			else
			{
				two[i][0] = -1;
			}
			
			
			
			if(five[0][i] != -1 && five[0][i-1] != -1)
			{
				five[0][i] += five[0][i-1];
			}
			else
			{
				five[0][i] = -1;
			}
			
			
			
			if(five[i][0] != -1 && five[i-1][0] != -1)
			{
				five[i][0] += five[i-1][0];
			}
			else
			{
				five[i][0] = -1;
			}
			
			
		}
	
		
		
		
		for(int i = 1; i < N; i++)
		{
			for(int j =1; j <N; j++)
			{
				
				
				if(two[i][j] != -1)
				{
					if((two[i-1][j] == -1 && two[i][j-1] == -1) )
					{
						two[i][j] = -1;
					}
					else if(two[i-1][j] == -1)
					{
						two[i][j] += two[i][j-1];
					}
					else if(two[i][j-1] == -1)
					{
						two[i][j] += two[i-1][j];
					}
					else
					{
						two[i][j] += min(two[i][j-1],two[i-1][j]);
					}
				}
				
				if(five[i][j] != -1)
				{
					if((five[i-1][j] == -1 && five[i][j-1] == -1) )
					{
						five[i][j] = -1;
					}
					else if(five[i-1][j] == -1)
					{
						five[i][j] += five[i][j-1];
					}
					else if(five[i][j-1] == -1)
					{
						five[i][j] += five[i-1][j];
					}
					else
					{
						five[i][j] += min(five[i][j-1],five[i-1][j]);
					}
				}
				
				
			}
			
			
		}
		
		result = min(two[N-1][N-1],five[N-1][N-1]);
		
		cout << "#"<<tc<<" "<<result <<endl;
		
		
		
		
	}
	
	
	
	
	
	
	
	
	
	return 0;
	
}