22.08.22. 풀었던 문제들

백준 단계별 28 DP와 역추적

14002 LIS 4

14003 LIS 5 - 이 2개는 예전에 푼 적 있었다.

12852 1로 만들기 2 - 답부터 거꾸로 찾아가면 됨. 말 그대로 역추적.

void solve(){
	int N; cin>>N;
	int INF = 987654321;
	vector<int> dp(N+1, INF); 
	vector<int> prev(N+1); // prev[i] : i 이전에 온 수

	dp[0] = 1; dp[1] = 0;
	for(int i = 2; i<=N; i++){
		dp[i] = dp[i-1] + 1; // dp[i]를 갱신하면 dp[i-1]도 바로 갱신한다.
		prev[i] = i-1;

		if(i%2 == 0){
			if(dp[i] > dp[i/2] + 1){
				dp[i] = dp[i/2] + 1;
				prev[i] = i/2;
			}
		}
		if(i%3 == 0){
			if(dp[i] > dp[i/3] + 1){
				dp[i] = dp[i/3] + 1;
				prev[i] = i/3;
			}
		}
	}
	cout<<dp[N]<<'\n';
	while(N != 0){
		cout<<N<<' ';
		N = prev[N];
	}
}

9252 LCS 2 - 마찬가지. 답부터 거꾸로 찾아가면 됨. 말 그대로 역추적이다. 괜히 억지로 0부터 찾아가지 말자.

void solve(){
	string A, B; cin>>A>>B;
	vector<vector<int>> dp(A.size()+1, vector<int>(B.size()+1, 0));
	// dp[i][j] : A는 i까지, B는 j까지 봤을 때 LCS
	for(int r = 1; r<=A.size(); r++){
		for(int c = 1; c<=B.size(); c++){
			dp[r][c] = max(dp[r-1][c], dp[r][c-1]);
			if(A[r-1] == B[c-1]){
				dp[r][c] = dp[r-1][c-1] + 1;
			}
		}
	}

	/int cnt = dp[A.size()][B.size()];
	cout<<cnt<<'\n';

	int r = A.size(), c = B.size();
	vector<char> answer(cnt);
	while(dp[r][c] != 0){
		while(r > 1 && dp[r-1][c] == dp[r][c]){
			r--;
		}
		while(c > 1 && dp[r][c-1] == dp[r][c]){
			c--;
		}
		answer[cnt-1] = A[r-1];
		cnt--;
		r--; c--;
	}
	for(char elem : answer) cout<<elem;
}