Boj 2625) Dna 유사도

문제

백준 2625

설명

이 글에선 내가 문제이해를 위해 필요했던 부분을 위주로 작성하려고 한다.

여기에 추가로 Slllju Blog 를 참고하였다.

DP

기본적인 DP 전략은 LCS 랑 비슷하다. 비교할 문자열이 두개이므로 2차원 DP 를 만들고 건너뛰어서 도달할 수 있는 이전 DP 값이 있으면 그 값을 이용해 점화식을 구성한다.

이때 사전순에 따른 문자열 구성의 편의를 위해 문자열 끝부분부터 점화식을 돌리는게 좋다. 그래야지 문자열 맨 앞부분의 dp[][] 값이 K-LCS 의 길이가 되어 공통서열의 앞부분을 문자열 구성의 시작점으로 잡기 편하기 때문이다.

주어진 문자열의 길이가 N = 1000 이고 k<=30 이므로 O(N^2 * K) 로 구성해도 된다. 하지만 Sliding Window 기법을 이용해 O(N^2 * K) 로 줄일 수도 있다.

• 편의상 이차원 dp[row][col] 에서 Row 를 A 문자열 위치로 두고 Col 을 B 문자열 위치라고 두자. 그러면 아래 코드는 Column 부터 먼저 검사한다고 볼 수 있다. 이때 Row 가 바뀌지 않는 한 같은 Column 의 연속된 k 개의 Dp 값, 즉 dp[a+(1~k+1)][b] 중의 최적값은 재사용 될 수 있다. deque 을 이용해 K 개의 Dp 값을 유지할 수도 있지만 크기가 크지 않으므로 아래 코드는 문자열크기의 배열에 값을 저장했다.

사전순에 따른 문자열 구성

문제의 핵심이 되는 부분이다. 실수하기가 매우 좋다.

나는 dp[][] 에 다음 dp[][] 상의 위치를 기록해서 타고가는 그리디 전략을 처음에 사용하려고 했다. 하지만 이는 성립하지 않는데, 왜냐하면 바로 이전 위치의 문자가 같으면 그 이전의 문자를 다시 봐야하기 때문이다. 바로 직전 문자만으로는 판단할 수 없는 경우가 생긴다.

그래서 모든 경우를 세야하는데 이때 사용하는 것이 BFS 이다. 직전 문자가 같은 경우들을 queue 에 넣어서 모든 경우를 셈하는 것이다. 구현은 의외로 간단한데 매 Node 마다 완전탐색을 돌리고, 가장 사전순으로 빠른 Node 들만 다시 queue 에 넣어서 BFS 를 돌리는 것이다.

이때 아래 코드는 계수정렬을 이용해서 사전순으로 가장빠른 Node 들을 분리했다.

시간 복잡도

O(\(\mathrm{N}^2 \mathrm{K}^2\))

• 아래의 BFS 부분은 시간복잡도가 어떤지 잘 모르겠어서 러프하게 잡음.

코드

int k;
int sa, sb;
string A, B;
int dp[1001][1001], dp2[1001];

string Do()
{
	// 2차원 DP
    int max_len = 0;
    for(int a = sa - 1; a >= 0; a--)
        for (int b = sb - 1; b >= 0; b--)
        {   
            int tmp = dp2[b] = 0;
            for (int o = 1; o <= k + 1; o++)
            {
                if(a+o < sa) dp2[b] = max(dp2[b], dp[a+o][b]);
                if(b+o < sb) tmp = max(tmp, dp2[b+o]);
            }
            if (A[a] == B[b]) {              
                max_len = max(max_len, dp[a][b] = tmp + 1);
            }

            //if (A[a] != B[b]) continue;
            //for (int ka = 1; ka <= k + 1; ka++)
            //    for (int kb = 1; kb <= k + 1; kb++)
            //    {
            //        if (a + ka >= sa || b + kb >= sb) continue;                 
            //        dp[a][b] = max(dp[a][b], dp[a + ka][b + kb]);
            //    }
            //max_len = max(max_len, ++dp[a][b]);
        }

	// BFS 준비
    queue<pair<int, int>> q[256];
    for (int x = sa - 1; x >= 0; x--)
        for (int y = sb - 1; y >= 0; y--)
            if (dp[x][y] == max_len) 
                q[A[x]].push({ x, y });

    string ans;

	// BFS
    while (max_len)
    {
		// 계수 정렬을 사용해서 사전상 가장 빠른 queue 를 선택하고 나머진 비운다.
        queue<pair<int, int>>* cur_q = nullptr;
        for (int i = 0; i < 256; i++)
            if (!q[i].empty())
            {
                if (!cur_q) {
                    cur_q = q + i;
                    ans += char(i);
                }
                else {
                    queue<pair<int, int>> qq;
                    swap(qq, q[i]);
                }
            }

        max_len--;

		// BFS 를 돌리는 중에 queue 에 위치가 추가될 수 있으므로 size 만큼 BFS 를 한다. 
        int size = cur_q->size();
        while (size--)
        {
            pair<int,int> cur = cur_q->front(); cur_q->pop();
            for (int ka = 1; ka <= k + 1; ka++)
                for (int kb = 1; kb <= k + 1; kb++)
                {
                    if (cur.first + ka < sa && cur.second + kb < sb && dp[cur.first + ka][cur.second + kb] == max_len)
                    {
                        q[A[cur.first+ka]].push({ cur.first + ka, cur.second + kb });
                        dp[cur.first + ka][cur.second + kb] = 0;
                    }
                }
        }
    }
    return ans;
}


int main()
{
	fastio;

	cin >> k;
	cin >> sa; cin >> A;
	cin >> sb; cin >> B;

    cout << Do();
}

/*
AGTCAC, GATGAGAC, K = 2

      G A T G A G A C
    A 0 3 0 0 3 0 1 0 
    G 3 0 0 1 0 2 0 0
    T 0 0 2 0 0 0 0 0
    C 0 0 0 0 0 0 0 1
    A 0 1 0 0 1 0 2 0
    C 0 0 0 0 0 0 0 1
*/