[ boj : 2806 ] DNA 발견

www.acmicpc.net/problem/2806

2806번: DNA 발견

문제 : 2가지의 돌연변이가 존재합니다. 1번은 현재 글자만 바꿀 수 있고 2번은 첫문자부터 k 번 문자까지 전부 다른 문자로 뒤집을 수 있습니다.

 

해설 : 뭔가 문제가 너무 '그럴듯'하게 보였어요. 무슨 뜻이냐면 그냥 현재 당장 최선의 선택을 하면 답이 나올 것이라고 생각했습니다. 한마디로 '그리디'하게 말이죠. 그런데 잘못 생각했더라구요.....증명은 하지 못했으니 그리디 하게 풀지는 못했으니 이건 넘어가겠습니다.

 

DP를 이용해서 풀었습니다. 결국 전부 A를 만들어야 되니 현재 동작하기 전 상태를 참고하여 현재 동작을 입혀야겠죠.

즉, 현재까지 문자가 전부 A이거나 전부 B이거나 이 두 상태로 만들어야 된다는 뜻입니다. 그리고 나서 새로운 문자를 확인했을때 A인지 B인지에 따라 동작을 해주면 됩니다.

 

1)현재 문자가 A이고 모두 A로 만들고 싶은 경우/ 현재 문자가 A이고 모두 B로 만들고 싶은 경우

2)현재 문자가 B이고 모두 A로 만들고 싶은 경우 / 현재 문자가 B이고 모두 B로 만들고 싶은 경우

 

이를 다시 나눌 수 있겠죠.

현재 문자가 A이고 모두 A로 만들고 싶은 경우에 1)지금까지 모두 A인 상태를 그대로 가져오는 경우 2)지금까지 B인 상태에서 전부 뒤집고 나서 가져오는 경우 

이렇게 말이죠. 그럼 전자는 그냥 i-1 의 상태를 가져오면 되고 후자는 i-1 상태에서 +1 을 해주면 되겠죠. 이 중 더 작은값을 저장해 주면 됩니다.

 

모든 경우에 이를 적용해 주면 됩니다.

 

#include<bits/stdc++.h>

using namespace std;

int dp[2][1000000];

int main()
{
	int n;
	string s;
	cin >> n >> s;

	for (int i = 0; i < n; i++)
		dp[0][i] = dp[1][i] = (int)1e9;
	if (s[0] == 'A')
		dp[0][0] = 0, dp[1][0] = 1;
	else
		dp[0][0] = 1, dp[1][0] = 0;

	for (int i = 1; i < n; i++) {
		if (s[i] == 'A') {
			dp[0][i] = min(dp[0][i - 1], dp[1][i - 1] + 1);
			dp[1][i] = min(dp[0][i - 1] + 1, dp[1][i - 1] + 1);
		}
		else {
			dp[0][i] = min(dp[0][i - 1] + 1, dp[1][i - 1]+1);
			dp[1][i] = min(dp[0][i - 1] + 1, dp[1][i - 1]);
		}
	}
	cout << dp[0][n - 1];
	return 0;
}