BOJ 1369 - 배열값

BOJ 1369 - 배열값

그리디하게 항상 2가 가장 적게 나오는 경로나 5가 가장 적게 나오는 경로 중 답이 있음을 관찰한다.

그렇게 DP를 두번 돌려서 적은것이 정답이다.

void solve() {  
   int n;  
   cin >> n;  
   vvi b(n, vi(n));  
   auto two = b;  
   auto five = b;  
   fv2(b);  
   for (int y = 0; y < n; y++)  
      for (int x = 0; x < n; x++) {  
         if (b[y][x] == 0) continue;  
         int t = 0;  
         int f = 0;  
         while (b[y][x] % 2 == 0) t++, b[y][x] /= 2;  
         while (b[y][x] % 5 == 0) f++, b[y][x] /= 5;  
         two[y][x] = t, five[y][x] = f;  
      }  
  
   vvi five_cnt(n, vi(n, 1e9)), two_cnt(n, vi(n, 1e9));  
   five_cnt[0][0] = five[0][0];  
   two_cnt[0][0] = two[0][0];  
   for (int y = 0; y < n; y++) {  
      for (int x = 0; x < n; x++) {  
         if (!y && !x || b[y][x] == 0) continue;  
         if (y) {  
            five_cnt[y][x] = min(five_cnt[y][x], five_cnt[y - 1][x] + five[y][x]);  
            two_cnt[y][x] = min(two_cnt[y][x], two_cnt[y - 1][x] + two[y][x]);  
         }  
         if (x) {  
            five_cnt[y][x] = min(five_cnt[y][x], five_cnt[y][x - 1] + five[y][x]);  
            two_cnt[y][x] = min(two_cnt[y][x], two_cnt[y][x - 1] + two[y][x]);  
         }  
      }  
   }  
   cout << min(two_cnt[n - 1][n - 1], five_cnt[n - 1][n - 1]);  
}