배열값
시간 제한2초메모리 제한128 MB
N by N 격자에서 0인 칸을 피해 왼쪽 위에서 오른쪽 아래로 가는 경로 중, 방문한 값들의 곱에서 끝자리 0의 개수를 최소로 만드는 값을 구합니다.
문제
가로와 세로가 각각 N칸인 정사각형 배열이 있다. 각 칸에는 음이 아닌 정수가 하나 적혀 있다.
(1, 1)에서 (N, N)까지 이동하려고 한다. 한 번 이동할 때는 현재 칸의 오른쪽 칸 또는 아래쪽 칸으로만 갈 수 있으며, 배열 밖으로 나갈 수 없다. 값이 0인 칸으로는 이동할 수 없다.
하나의 경로는 시작 칸과 도착 칸을 포함해 모두 2N-1개의 칸을 지난다. 그 경로에서 지나간 칸들에 적힌 수를 모두 곱한 값을 그 경로의 경로값이라고 한다.
가능한 모든 경로 중에서 경로값의 끝자리 0의 개수가 가장 적을 때, 그 최소 개수를 이 배열의 배열값이라고 한다. 배열이 주어졌을 때 배열값을 구하라.
입력은 항상 (1, 1)에서 (N, N)까지 이동할 수 있는 경우만 주어진다.
입력
첫째 줄에 배열의 크기 N이 주어진다. (2 <= N <= 1,000)
다음 N개의 줄에는 배열에 적힌 정수 N개가 공백으로 구분되어 주어진다. 각 정수는 0 이상 1,000,000 이하이다.
출력
첫째 줄에 배열값을 출력한다.