1369번 : 배열값

https://www.acmicpc.net/problem/1369

1369번: 배열값

(1,1) ~ (N,N) 도달 중 만나는 수들을 곱할 때 뒤에 생기는 0의 최솟값을 구하는 문제다.

아이디어 : 

뒤에 생기는 0의 개수라는 것은, 곧 2와 5의 개수 중 최솟값이라는 소리다. 따라서 2의 개수와 5의 개수에만 집중해보자.
최솟값을 구하려면, 2를 최소로 만들거나, 5를 최소로 만들어야 한다. 

어떤 칸에 도달하려면, 위에서 내려오거나, 왼쪽에서 와야한다.

여기까지 dp식을 세울 수 있다.
pair<int,int> dp[2][1001][1001]으로 세울 수 있고,
dp[0][i][j] : (i,j)칸에 도달했고, 2의 개수를 최소로 만들 때 누적된 2와 5의 개수
dp[1][i][j] : (i,j)칸에 도달했고, 5의 개수를 최소로 만들 때 누적된 2와 5의 개수
이렇게 정의할 수 있다.

dp식을 구하는 방법은 : 
  dp[0][i-1][j]
  dp[1][i-1][j]
  dp[0][i][j-1]
  dp[1][i][j-1]
이 4가지 방법 중 2의 개수가 가장 작은 것을 dp[0][i][j]에, 5의 개수가 가장 작은 것을 dp[1][i][j]에 넣어주면 된다.

구현 : 

우선 나올 수 있는 수인 1~1000000까지 각각 2와 5의 개수만 구해준다.
만약 어떤 수 i가 2로 나누어 떨어진다면, i의 2의 개수는 i/2의 2의 개수+1이고, i의 5의 개수는 i/2의 5의 개수이다.
만약 어떤 수 i가 5로 나누어 떨어진다면, i의 2의 개수는 i/5의 2의 개수이고, i의 5의 개수는 i/5의 5의 개수+1이다.

이중for문을 돌면서 dp값을 다 채우고, dp[0][N][N]과 dp[1][N][N] 중 min(2의개수, 5의개수)가 더 적은 것을 출력한다.

0을 방문하지 않음에 유의하면서 구현한다.

코드 : 

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
const int INF=987654231;
pii cache[1000001];
int arr[1111][1111];
pii dp[2][1111][1111];
pii padd(pii x, pii y){
	pii ret={x.first+y.first, x.second+y.second};
	if(ret.first>INF) ret.first=INF;
	if(ret.second>INF) ret.second=INF;
	return ret;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int N; cin>>N;
	for(int i=1; i<=1000000; ++i){
		if(i%2==0){
			cache[i]=cache[i/2];
			cache[i].first++;
		}
		else if(i%5==0){
			cache[i]=cache[i/5];
			cache[i].second++;
		}
	}
	
	for(int i=1; i<=N; ++i){
		for(int j=1; j<=N; ++j){
			cin>>arr[i][j];
			if(arr[i][j]==0){
				continue;
			}
			vector<pii> v2; // {0up, 0left, 1up, 1left}
			vector<pii> v5; // {0up, 0left, 1up, 1left}
			for(int k=0; k<=1; ++k){
				if(arr[i-1][j]!=0) v2.push_back(padd(dp[k][i-1][j], cache[arr[i][j]]));
				if(arr[i-1][j]!=0) v5.push_back(padd(dp[k][i-1][j], cache[arr[i][j]]));
				if(arr[i][j-1]!=0) v2.push_back(padd(dp[k][i][j-1], cache[arr[i][j]]));
				if(arr[i][j-1]!=0) v5.push_back(padd(dp[k][i][j-1], cache[arr[i][j]]));
			}
			if(i==1 && j==1){
				v2.push_back(cache[arr[i][j]]);
				v5.push_back(cache[arr[i][j]]);
			}
			if(v2.empty() || v5.empty()){
				dp[0][i][j]={INF,INF};
				dp[1][i][j]={INF,INF};
			}
			else{
				sort(v2.begin(), v2.end(), [](pii x, pii y){
					if(x.first==y.first) return x.second<y.second;
					return x.first<y.first;
				});
				dp[0][i][j]=v2[0];
				sort(v5.begin(), v5.end(), [](pii x, pii y){
					if(x.second==y.second) return x.first<y.first;
					return x.second<y.second;
				});
				dp[1][i][j]=v5[0];
			}
		}
	}
	// for(int i=1; i<=N; ++i){
	// 	for(int j=1; j<=N; ++j){
	// 		cout << "dp[0]["<<i<<"]["<<j<<"]="<<dp[0][i][j].first << ", " << dp[0][i][j].second<<'\n';
	// 		cout << "dp[1]["<<i<<"]["<<j<<"]="<<dp[1][i][j].first << ", " << dp[1][i][j].second<<'\n';
	// 	}
	// }
	int res=min(min(dp[0][N][N].first, dp[0][N][N].second),min(dp[1][N][N].first, dp[1][N][N].second));
	if(arr[N][N]==0){
		cout << 0 << '\n';
	}
	else{
		cout << res << '\n';
	}
}