백준 / 3188 / nule / C++

문제 링크 : https://www.acmicpc.net/problem/3188

#include <bits/stdc++.h>
#define maxval 5000000

using namespace std;

vector<vector<pair<int,int>>> arr;

void calc(int i, int j, int num)
{
    if(num == 0)
    {
        return;
    }

    int tcount = 0;
    int fcount = 0;
    while(num % 5 == 0)
    {
        fcount++;
        num /= 5;
    }
    while(num % 2 == 0)
    {
        tcount++;
        num /= 2;
    }
    arr[i][j].first = tcount;
    arr[i][j].second = fcount;
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    int n;
    cin >> n;
    arr.resize(n,vector<pair<int,int>>(n,{maxval,maxval}));

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            int num;
            cin >> num;
            calc(i,j,num);
        }
    }

    vector<vector<pair<int, int>>> dp(n, vector<pair<int, int>>(n, {maxval, maxval}));
    dp[0][0] = arr[0][0];

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(arr[i][j].first == maxval && arr[i][j].second == maxval)
            {
                continue;
            }

            if(i > 0)
            {
                dp[i][j].first = min(dp[i][j].first, dp[i-1][j].first + arr[i][j].first);
                dp[i][j].second = min(dp[i][j].second, dp[i-1][j].second + arr[i][j].second);
            }
            if(j > 0)
            {
                dp[i][j].first = min(dp[i][j].first, dp[i][j-1].first + arr[i][j].first);
                dp[i][j].second = min(dp[i][j].second, dp[i][j-1].second + arr[i][j].second);
            }
        }
    }

    int result = min(dp[n-1][n-1].first, dp[n-1][n-1].second);
    cout << result << "\n";

    return 0;
}

얼핏 보면 그래프 탐색 문제 같지만, 이 문제는 최적 경로 라는 개념을 직접 정의했고, 최적 경로의 정의는 다음과 같다.

지나온 경로의 모든 정수를 곱한 값을 10진수로 표현했을 때, 끝에 있는 0의 개수가 최소가 되는 경우

이걸 풀어서 본다면 결국 지나온 값의 인수 중 2와 5의 쌍이 몇 개가 만들어지는가? 그리고 그 최솟값은 얼마인가? 로 볼 수 있다.

따라서 처음 초기 배열을 입력받을 때 pair쌍으로 2와 5의 인수 개수를 저장한 후, 바텀 업 방식을 통해 인수의 개수가 최소가 되는 값을 이중 for문으로 갱신하여 해결했다.

오랜만에 푸는 백준이라 그런지 실버에서도 헤맨다... @-@