Hiho #1241: Best Route in a Grid [dp Quality in 2와 5의 최소 일치 개수]

제목 링크:나를 누르다
제목: n*n의 그림이 있고 위치마다 마이너스 수치가 있습니다.지금 당신은 왼쪽 상단에서 오른쪽 하단까지 가려고 합니다. 매번 아래나 오른쪽으로만 갈 수 있고, 수치가 0인 점은 갈 수 없습니다.우리는 지나간 위치의 수치를 누승하여 T를 얻었다.-- T 말미 연속 0의 개수는 최소 몇이냐.
사고방식: 2*5=10 때문에 0을 얻는다.우리는 먼저 질인자 5의 개수를 미리 처리하고 왼쪽 상단에서 오른쪽 하단까지 dp를 한 번 달리며 T에서 가장 적은 5의 개수ans1을 구한다.그리고 질량 인자 2의 개수를 미리 처리하고 dp를 한 번 더 뛰며 T에서 가장 적은 2개의 개수ans2를 구한다.정답은 민(ans1,ans2)입니다.
AC 코드:

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 1001
#define INF 0x3f3f3f3f
using namespace std;
int val[MAXN][MAXN];
int dp[MAXN][MAXN];
int Map[MAXN][MAXN];
int main()
{
    int n;
    while(scanf("%d", &n) != EOF)
    {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                scanf("%d", &Map[i][j]);
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(Map[i][j] == 0)
                    val[i][j] = INF;
                else
                {
                    int cnt = 0;
                    int num = Map[i][j];
                    while(num % 5 == 0)
                        cnt++, num /= 5;
                    val[i][j] = cnt;
                }
            }
        }
        memset(dp, INF, sizeof(dp));
        dp[1][1] = val[1][1];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = min(dp[i][j], min(dp[i-1][j], dp[i][j-1])+val[i][j]);
        int ans = dp[n][n];
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(Map[i][j] == 0)
                    val[i][j] = INF;
                else
                {
                    int cnt = 0;
                    int num = Map[i][j];
                    while(num % 2 == 0)
                        cnt++, num /= 2;
                    val[i][j] = cnt;
                }
            }
        }
        memset(dp, INF, sizeof(dp));
        dp[1][1] = val[1][1];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = min(dp[i][j], min(dp[i-1][j], dp[i][j-1])+val[i][j]);
        ans = min(ans, dp[n][n]);
        printf("%d
", ans);
    }
    return 0;
}