시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 73 19 16 41.026%

문제

가로 N칸, 세로 N칸으로 되어 있는 정사각형 모양의 배열이 있고, 배열의 각 칸에는 음이 아닌 정수가 하나씩 적혀져 있다. 우리는 이 배열의 배열값을 다음과 같이 찾고자 한다.

배열의 왼쪽 위 칸인 (1, 1)에서 오른쪽 아래 칸인 (N, N)으로의 이동을 생각할 수 있다. 이동할 때는 반드시 현재 위치의 아래 칸이나, 현재 위치의 오른쪽 칸으로만 이동할 수 있다. 물론, 배열 밖으로 나갈 수는 없다. 또한 하나의 제약이 더 있는데, 그 칸에 적혀져 있는 정수가 0인 경우에는 그 칸으로 이동할 수 없다.

이렇게 (1, 1)에서 (N, N)까지 이동하는 경로는 여러 가지가 있을 수 있다. 우리는 이러한 각각의 경로에 대해서 경로값을 정의할 수 있는데, 이동하면서 거쳐 온 2N-1개의 칸에 적혀 있는 모든 정수의 곱을 이 경로의 경로값으로 정의한다. 예를 들어 N=3이고 배열이 아래와 같은 모양이라고 할 때, 거쳐 온 칸에 적혀 있는 정수가 1, 2, 3, 5, 8이 되도록 이동했다면 이 경우 경로값은 240(=1×2×3×5×8)이 된다.

주어진 배열에서 (1, 1)부터 (N, N)까지 이동하는 경로는 매우 많을 수 있으므로, 경로값 또한 다양하게 나타날 수 있다. 이러한 모든 경로값 중에서, 경로값을 나타내는 자연수의 끝자리 0의 개수가 가장 적을 때, 그 0의 개수를 이 배열의 배열값으로 정의한다. 위 배열의 경우 1, 4, 6, 7, 8의 경로로 이동하면 경로값이 1344(=1×4×6×7×8)이 되므로, 이 경우가 끝자리 0의 개수가 가장 적은 경우이다. (240은 끝자리 0의 개수가 1개이므로 0개보다 많다) 따라서 위 배열의 배열값은 0이 된다.

배열이 주어지면 그 배열의 배열값을 계산하는 프로그램을 작성하시오. 항상 (1, 1)에서 (N, N)으로 이동하는 경로가 존재하는 데이터만이 입력으로 들어온다.

입력

첫째 줄에 배열의 크기를 나타내는 자연수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 배열에 적힌 수를 나타내는 정수가 각각 N개씩 빈 칸을 사이에 두고 들어온다. 입력되는 정수는 음 아닌 정수로 그 크기는 1,000,000을 넘지 않는다.

출력

첫째 줄에 이 배열의 배열값을 출력한다.

예제 입력

3
1 2 3
4 0 5
6 7 8

예제 출력

0

힌트

출처

  • 문제를 번역한 사람: author5