7673

static int N;
static int board[1000][1000][4]; // 10의 개수, 2의 개수, 5의 개수, 원래 수
static int table[1000001][4]; //10의 개수, 2의 개수, 5의 개수, hit/miss
static bool visit[1000][1000]; 
static queue<pair<int, int>> q;

static int d[2][2] = {
	0, 1, //right
	1, 0 //down
};

static void translation(int n)
{
	int cp = n;
	int divs[] = { 10, 2, 5 };

	if (table[cp][3] || cp == 0)
		return;

	for (int i = 0; i < 3; i++)
	{
		int cnt = 0;

		while (n % divs[i] == 0)
		{
			n /= divs[i];
			cnt += 1;
		}
		table[cp][i] = cnt;
	}

	table[cp][3] = 1;
}

static int solution(void)
{
	int ret = 0, v;

	scanf("%d", &N);
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			scanf("%d", &board[y][x][3]);
			translation(board[y][x][3]);
			for (int i = 0; i < 3; i++)
				board[y][x][i] = table[board[y][x][3]][i];
		}
	}

	memset(visit, false, sizeof(visit));

	q.push({ 0,0 });
	visit[0][0] = true;
	
	while (!q.empty())
	{
		pair<int, int> c = q.front();
		q.pop();

		int y = c.first, x = c.second;

		for (int i = 0; i < 2; i++)
		{
			int ny = y + d[i][0];
			int nx = x + d[i][1];

			v = board[ny][nx][3];

			if (ny < N && nx < N && v > 0)
			{
				int ten = table[v][0], two = table[v][1], five = table[v][2];

				ten += board[y][x][0];
				two += board[y][x][1];
				five += board[y][x][2];

				int min = two < five ? two : five;

				ten += min;
				two -= min;
				five -= min;

				if (!visit[ny][nx] || ten < board[ny][nx][0])
				{
					board[ny][nx][0] = ten;
					board[ny][nx][1] = two;
					board[ny][nx][2] = five;
				}

				if (!visit[ny][nx])
				{
					q.push({ ny, nx });
					visit[ny][nx] = true;
				}
			}
		}
	}

	return board[N - 1][N - 1][0];
}

재귀 형식의 dfs로 풀면 타임아웃이 발생할 수 있고, 더욱이 곱연산으로 인한 오버플로우 문제 등 이 있다.

갈수 있는 경로가 오른쪽 또는 아래쪽이므로, 좌상단에서 우하단으로 확산하듯이 배열을 순환하면서

하위에 연속되는 0의 개수가 최소가 되게 구할 수 있다.

 

연속되는 0의 개수는 10^n 이 해당 값에 얼마나 포함되는지를 알면 알 수 있다.

또 10은 소수인 2 와 5의 곱으로 구성되니,

10으로 먼저 나누고, 그 다음에 2, 5 또는 5, 2 순으로 나누어 가며 해당 값의 구성을 알 수 있다.

 

또 위 연산에 대해서 dp를 이용하면 불필요한 연산을 최소화 할 수 있다.