22.08.09. 풀었던 문제들

백준 단계별 24 DP 2

1520 내리막길

 bottom-up dp로는 풀면 안 되는 게, 순서대로 채워나가면 역순으로 오는 예외가 있다. 따라서 무조건 top-down dp로 풀어야 한다. 사실상 DFS인데 이전에 구한 값을 memoization해서 사용해야 하는, DFS + DP이다.

 DFS 하는 것처럼 도착점에 다다르면 +1, 그렇지 않다면 다다르는 경우에 대해서만 그 경우의 수를 더해주었다.

int dr[4] = {1, 0, -1, 0};
int dc[4] = {0, 1, 0, -1};
int board[501][501], dp[501][501];
int M, N;

int search(int r, int c){
	if(r == M-1 && c == N-1) return 1;
	if(dp[r][c] != -1) return dp[r][c];
	dp[r][c] = 0;
	for(int d = 0; d<4; d++){
		int nr = r + dr[d];
		int nc = c + dc[d];
		if(0 <= nr && nr < M && 0 <= nc && nc < N && board[r][c] > board[nr][nc]){
			dp[r][c] += search(nr, nc);
		}
	}
	return dp[r][c];
}

void solve(){
	cin>>M>>N;
	for(int r = 0; r<M; r++){
		for(int c = 0; c<N; c++){
			cin>>board[r][c];
			dp[r][c] = -1;
		}
	}
	cout<<search(0, 0)<<'\n';
}

 

10942 팰린드롬?

 dp[r][c]를 볼 때, 좌로1칸 아래로 1칸(r+1~c-1)이 팰린드롬이고 arr[r]과 arr[c]가 같으면 팰린드롬이다.

 그리고 대각선 접근하는 것 - 첫 for문은 element 차이(diff), 다음 for문은 시작하는 index(row)로 두면 뭔가 쉽다!

void solve(){
	int N; cin>>N;
	vector<int> arr(N);
	for(int i = 0; i<N; i++) cin>>arr[i];

	// dp initialize
	vector<vector<int>> dp(N, vector<int>(N, 0));
	for(int i = 0; i<N; i++){ // size 1 == 무조건 true
		dp[i][i] = true;
	}
	for(int i = 0; i<N-1; i++){ // size 2 == 같아야 true
		if(arr[i] == arr[i+1]) dp[i][i+1] = 1;
	}

	// dp
	for(int diff = 2; diff<N; diff++){ // 대각선 개수
		for(int r = 0; r<N-diff; r++){ // 한 대각선 당 채울 row 개수
			if(dp[r+1][r+diff-1] == 1 && (arr[r] == arr[r+diff])) dp[r][r+diff] = 1;
			// dp[r][r+diff]를 보면 됨
			
		}
	}

	/*

	0, 0	0, 1	0, 2	0, 3	0, 4
	    	1, 1	1, 2	1, 3	1, 4
		      		2, 2	2, 3	2, 4
					  		3, 3	3, 4
							  		4, 4

	// dp[r][c]를 볼 때, 좌로1칸 아래로 1칸(r+1~c-1)이 팰린드롬이고 arr[r]과 arr[c]가 같으면 팰린드롬.
	*/

	int M; cin>>M;
	while(M--){
		int S, E; cin>>S>>E;
		cout<<dp[S-1][E-1]<<'\n';
	}
}

 

2629 양팔저울

 dp[i][j]를 i번째 추까지 사용해서 무게 j를 측정할 수 있는지 여부로 두고 문제를 푼다면 쉽게 접근할 수 있다. 식 안에 들어가는 w - weights[i]도 냅색에서 봤던 것과 굉장히 유사하다.

 점화식은, 'dp[i-1]에서 들 수 있었던 모든 무게는 dp[i]에서도 들 수 있고, dp[i-1]에서 들 수 있었던 모든 무게 +- weights[i], 또는 weights[i] - w는 dp[i]에서 들 수 있다. 추가로, weights[i]도 dp[i]에서 들 수 있다'이다.

 2가지 실수를 했는데, 처음에는 dp를 40000의 1차원 배열로 둔 것. 이렇게 두면 방금 전까지 탐색했던 무게추를 또 쓰는 효과가 나서 오류가 난다.

 다음 실수는 dp[i][weights[i]]를 true로 두지 않은 것이다. 당연히 해 줘야 했었는데 실수했다.

void solve(){
	int n; cin>>n;
	vector<int> weights(n);
	for(int i = 0; i<n; i++){
		cin>>weights[i];
	}

	int target_n; cin>>target_n;
	vector<int> targets(target_n);
	for(int i = 0; i<target_n; i++){
		cin>>targets[i];
	}

	vector<vector<int>> dp(n, vector<int>(40001));
    // dp[i][j] : i번째 추까지 사용해서 무게 j를 측정할 수 있는지
	dp[0][weights[0]] = true;
	for(int i = 1; i<n; i++){
		dp[i][weights[i]] = true;
		for(int w = 0; w<=40000; w++){
			if(dp[i-1][w]){
				dp[i][w] = true;
				if(w + weights[i] <= 40000) dp[i][w+weights[i]] = true;
				if(w - weights[i] >= 0) dp[i][w-weights[i]] = true;
				if(weights[i] - w >= 0) dp[i][weights[i] - w] = true;
			}
		}
	}

	for(int targets : targets){
		if(dp[n-1][targets]) cout<<"Y ";
		else cout<<"N ";
	}
}

 

새로 추가된 앞선 문제들

3003 BIJELE

25304 영수증

25305 커트라인

다 기본 문젠데, 올 성공 떠 있지 않은 것이 킹받아서 슥 제출했다.