22.08.08. 풀었던 문제들

백준 단계별 24 DP 2

오랜만에 보니까 정신이 혼미하군. DP 1은 대부분 1차원 array에서 해결할 수 있는 문제(+한 방향으로만 진행하면서 규칙을 찾으면 되는)였다면 DP 2는 대부분 2차원 array에서 해결할 수 있는 문제 같다. dp[i][j] = min{dp[i][m] + dp[m+1][j]}라던가, ...

 

11066 파일 합치기

dp[i][j] : index i부터 index j까지 합치는 데 필요한 cost
두 파일을 합칠 때 필요한 cost = 두 파일 크기의 합이다.

 

그러면 
dp[i][i] = 0
dp[i][i+1] = files[i] + files[i+1]로 초기화 할 수 있고, 다음으로는

dp[i][i+2] = min{dp[i][i] + dp[i+1][i+2], dp[i][i+1] + dp[i+2][i+2]}(cost가 최소인 두 파일 선택) + psum(i, i+2) (두 파일 크기의 합)

이를 일반화하면...
dp[i][j] = min{dp[i][i] + dp[i+1][j], dp[i][i+1] + dp[i+2][j], ... , dp[i][j-1] + dp[j][j]} + psum(i, j)

이 된다.

정리하자면 dp[i][j] = dp[i][m] + dp[m+1][j] + ['i~m의 file sum' + 'm+1~j의 file sum']이다.
이 때 m이 어떤 값이듯 뒷항은 동일, 따라서 앞 항을 최소화하는 m을 찾기만 하면 된다.

vector<int> files;
vector<int> psum;
int INF = 999999999;

int getRangesum(int i, int j){ // return prefix sum from i to j
	int f = (i == 0 ? 0 : psum[i-1]);
	return psum[j] - f;
}

void solve(){
	int K; cin>>K;
	files.resize(K);
	psum.resize(K);
	for(int i = 0; i<K; i++){
		cin>>files[i];
		psum[i] = files[i];
		if(i != 0){
			psum[i] += psum[i-1];
		}
	}

	// dp initialize
	vector<vector<int>> dp(K, vector<int>(K, 0));
	for(int r = 0; r<K-1; r++){
		dp[r][r+1] = files[r] + files[r+1];
	}

	// do dp
	for(int diff = 2; diff<K; diff++){ // 대각선 개수 (총 K개, [i][i]와 [i][i+1]은 이미 했으니 K-2개를 해야 함)
		for(int r = 0; r<K-diff; r++){ // row 개수 (총 K개에서 대각선 개수만큼 빼야 함)
			dp[r][r+diff] = INF;
			for(int mid = 0; mid<diff; mid++){ // colmun 선택 가능한 개수 == 대각선 개후
				dp[r][r+diff] = min(dp[r][r+diff], dp[r][r+mid] + dp[r+mid+1][r+diff]);
			}
			dp[r][r+diff] += getRangesum(r, r+diff);
		}
	}

	cout<<dp[0][K-1]<<'\n';
}

 

11049 행렬 곱셈 순서

바로 위 문제랑 비슷한 문제. 2차원 dp의 최솟값 찾기 문제

 

dp[i][j] = {dp[i][m] + dp[m+1][j] + msize[i].first * msize[m].second * msize[j].second} 중 min값을 찾는 문제이다.

int INF = 999999999;

void solve(){
	int N; cin>>N;
	vector<pii> msize(N);
	for(int i = 0; i<N; i++){
		cin>>msize[i].first>>msize[i].second;
	}

	// dp initialize
	vector<vector<int>> dp(N, vector<int>(N, 0)); // dp[i][j] : i~j의 행렬곱의 min value
	/*for(int i = 0; i<N-1; i++){
		dp[i][i+1] = msize[i].first * msize[i].second * msize[i+1].second;
	}*/ // 이 문제에 한해, 초기화 할 필요가 없다
	for(int diag = 1; diag<N; diag++){ // 대각선 개수
		for(int r = 0; r<N-diag; r++){ // row
			dp[r][r+diag] = INF;
			for(int m = 0; m<diag; m++){ // mid
				dp[r][r+diag] = min(dp[r][r+diag], dp[r][r+m] + dp[r+m+1][r+diag] + msize[r].first * msize[r+m+1].first * msize[r+diag].second);
			}
		}
	}

	cout<<dp[0][N-1]<<'\n';
}