[BOJ-2806] DNA 발견

 

백준 2806 DNA 발견

 

2806번: DNA 발견

 

문제 설명

 

 - 국내 생물학자들이 신기한 DNA 분자를 발견했다.

 

 - 이 분자는 A와 B로만 이루어진 N글자로 나타낼 수 있다.

 

 - 이 분자는 계속해서 돌연변이를 한 다음 A로만 된 분자로 변한다.

 

 - 돌연변이는 두 종류가 있다.

 

 - 첫 번째 돌연변이는 분자의 한 글자가 다른 글자로 바뀌는 것이다.(A->B 또는 B->A)

 

 - 두 번째 돌연변이는 첫 K개 글자가 모두 다른 글자로 바뀌는 것이다.

 

 - DNA 분자가 주어졌을 때, 돌연변이를 최소 몇 번 일으키면, 전부 A로 된 분자가 되는지 구하라.

---

 

입력 값

 

 - 첫째 줄에 분자의 길이 N이 주어진다. ( 1 <= N <= 1,000,000 )

 

 - 둘째 줄에 분자를 이루는 N 글자가 주어진다.

 

---

 

 

예제

 

---

 

문제 분석

 

 - 돌연변이 분자는 A or B 두 문자 중 하나를 가지게 된다.

 

 - 돌연변이 분자는 총 길이가 N이기 때문에 모든 경우의 수는 $2^N$이 된다.

 

 - 즉, 모든 경우를 살펴보게 되면 $2^(100만)$이 되기 때문에, 모든 경우를 살펴 보는 방법은 옳지 않다.

 

 - 이 문제에서 핵심은 첫 K개의 문자를 한 번에 변화 시킬 수 있다는 것이다.

 

 - 즉, N개의 문자가 있을 때 N-1문자가 모두 B이면 한 번의 돌연변이를 일으켜서 모두 A로 변경할 수 있다는 것이다.

 

 - 이 방법을 응용하게 된다면, N-1번째 문자를 모두 A로 만드는 경우와 모두 B로 만드는 경우의 최소 값을 구하게 된다면

   N개의 문자를 모두 A로 만드는 최소 값을 구할 수 있다는 것이다.

 

 - 즉, 다이나믹 프로그래밍을 이용하면 간단하게 해결할 수 있다는 것이다. 

다이나믹 프로그래밍(Dynamic Programming, DP)

 

 - DP[0][j]를 j번째 문자까지를 모두 A로 만들 수 있는 최소의 경우의 수,

   DP[1][j]를 j번째 문자까지를 모두 B로 만들 수 있는 최소의 경우의 수 라고 하자.

 

 - DP[0][N]은 N번째 문자까지를 모두 A로 만들 수 있는 최소의 경우의 수가 된다.

 

 - N번째 문자가 A이면, DP[0][N] = min( DP[0][N-1], DP[1][N-1] + 1 ) 이 된다.

   N번째 문자가 A이기 떄문에 N-1까지 모두 A이면 더 이상 변화가 필요 없고,

   N-1까지 모두 B이면 1번 더 변화가 필요하기 때문이다.

 

 - N번째 문자가 B이면, DP[1][N] = min( DP[0][N-1] + 1 , DP[1][N-1] + 1 ) 이 된다.

   N번째 문자가 B이기 때문에 N-1까지 모두 A이면, 마지막 문자의 변화가 필요하고,

   N-1까지 모두 B이면, N번까지의 모든 B를 A로 변화가 필요하기 때문이다.

 

 - 초기값은 첫 문자가 A인 경우 DP[0][0] = 0, DP[1][0] = 1

   첫 문자가 B인 경우 DP[0][0] = 1, DP[0][1] = 0 이 된다. 

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>
#include<unordered_set>

using namespace std;


int dp[2][1000001];

int dir[] = { 'A','B' };

int changeString(int n,int d,string &s) {


	if (dp[d][n] == INT_MAX) {
		if (s[n] == dir[d]) {
			dp[d][n] = min(changeString(n - 1, d,s), changeString(n - 1, d^1,s) + 1);
		}
		else {
			dp[d][n] = min(changeString(n - 1, d, s)+1, changeString(n - 1, d^1, s) + 1);

		}
	}

	return dp[d][n];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	string s;

	cin >> N >> s;

	fill(&dp[0][0], &dp[0][0] + 2 * 1000001, INT_MAX);

	if (s[0] == 'A') {
		dp[0][0] = 0;
		dp[1][0] = 1;
	}
	else {
		dp[0][0] = 1;
		dp[1][0] = 0;
	}

	cout << changeString(N - 1, 0, s) << endl;




	return 0;
}