백준 1369 배열값

 

https://boj.ma/1369/t

1369번: 배열값

 

문제 요약

- 2차원 격자 왼쪽 위에서 출발하여 오른쪽이나 아래로만 이동하여 오른쪽아래 구석으로 도착하고싶다.

- 0인 칸으로는 이동이 불가능하다

- 방문했던 모든 칸의 숫자를 누적해서 곱한다.

- 오른쪽 아래 구석에 도착했을때, 곱한값의 끝자리 0의 개수가 가장 적게 하고 싶다.

- 끝자리 0의 개수를 가장 적게 했을때 그 때의 0의 개수를 출력

 

모든 경우를 확인한다고 생각해 보면,

N <= 1000 이고, N * N격자에서 규칙에 따라 이동 가능한 경우의 수는 O(2^(N*N)) 이 됩니다.

 

관찰

문제에서 원하는건 "끝자리 0의 개수 줄이기" 입니다.

끝자리가 0이 나오려면 어떤 수든 10이 곱해지면 0이 추가됩니다.

10 = 2 * 5입니다.

 

따라서, 격자의 각 칸에 쓰여져있는 수가 뭔지는 별로 중요하지 않습니다.

각 칸의 수가 2를 몇 개, 5를 몇 개 들고있는지만 알면 됩니다. 

 

(0, 0)에서 출발하여 (n - 1, n - 1)까지 이동하면서 2를 최소로 만나는 경우,

(0, 0)에서 출발하여 (n - 1, n - 1)까지 이동하면서 5를 최소로 만나는 경우

2가지를 각각 구해서 둘 중 최소값이 정답입니다.

 

각 경우는 dp를 이용해 구할 수 있습니다.

 

전처리후 dp 때리면 끝

 

 

코드(c++)

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <string.h>
#include <vector>
#include <set>
#include <unordered_map>

#define INF 0x3f3f3f3f
#define LINF 1e18+5
#define NM 1001010
#define endl '\n'
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};

int kdx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int kdy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};


int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> arr(n, vector<int>(n)), is_zero(n, vector<int>(n, 0)), arr2(n, vector<int>(n, 0))
    , arr5(n, vector<int>(n, 0)), dp2(n, vector<int>(n, -1)), dp5(n, vector<int>(n, -1));

    auto get_cnt = [&](int x, int prime) -> int {
        int cnt = 0;
        while (x % prime == 0) {cnt++; x/=prime;}
        return cnt;
    };

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 0) is_zero[i][j] = 1;
            else {
                arr2[i][j] = get_cnt(arr[i][j], 2);
                arr5[i][j] = get_cnt(arr[i][j], 5);
            }
        }
    }


    auto recur2 = [&](const auto&self, int x, int y) -> int {
        if (x >= n || y >= n) return INF;
        if (is_zero[x][y]) return INF;
        if (x == n - 1 && y == n - 1) return arr2[x][y];
        int&ret = dp2[x][y];
        if (~ret) return ret;
        ret = INF;
        return ret = min(ret,  min(self(self,x, y + 1), self(self, x + 1, y)) + arr2[x][y]);
    };


    auto recur5 = [&](const auto&self, int x, int y) -> int {
        if (x >= n || y >= n) return INF;
        if (is_zero[x][y]) return INF;
        if (x == n - 1 && y == n - 1) return arr5[x][y];
        int&ret = dp5[x][y];
        if (~ret) return ret;
        ret = INF;
        return ret = min(ret,  min(self(self,x, y + 1), self(self, x + 1, y)) + arr5[x][y]);
    };

    cout << min(recur2(recur2, 0, 0), recur5(recur5, 0, 0));



    return 0;
}