[백준] 1958번: LCS 3

https://www.acmicpc.net/problem/1958

1958번: LCS 3

---

문자열 3개의 LCS 길이를 구하는 dp 문제다.

 

1. 문제 조건

1) 문자열 3개의 LCS 길이를 출력한다.

2) 문자열은 알파벳 소문자로만 이루어져 있다.

3) 문자열의 길이는 100 이하다.

 

2. dp 배열 정의

문자열 2개의 LCS 길이를 구하는 dp 문제는 많이 풀어 봤다.

이 문제도 별로 다를 것 없이

문자열의 인덱스마다 LCS 길이를 저장하는 dp 배열을 만들어주면 된다.

 

문자열이 총 3개이므로 3차원 dp 배열을 만든다.

#define MAXL 101

char str1[MAXL];
char str2[MAXL];
char str3[MAXL];

// dp[i][j][k] = str1[i], str2[j], str3[k] 까지의 LCS 길이
int dp[MAXL][MAXL][MAXL];

 

3. 해결법

문자열이 3개일 때의 LCS 길이는

현재 보고 있는 각 문자열의 위치에 해당하는 글자가 모두 같을 때에만 1 증가한다.

그렇지 않다면 각 문자별로 이전 위치에 해당하는 LCS 길이 중 최댓값을 가져오면 된다.

 

dp 배열을 bottom-up 방식으로 구성하면 된다.

int i, j, k;
for(i=0; str1[i]!='\0'; i++) {
    for(j=0; str2[j]!='\0'; j++) {
        for(k=0; str3[k]!='\0'; k++) {
        	// 3글자가 모두 같은 경우, LCS 는 1 증가한다.
            if(str1[i] == str2[j] && str2[j] == str3[k])
                dp[i+1][j+1][k+1] = dp[i][j][k] + 1;
            else
                dp[i+1][j+1][k+1] = max(dp[i][j+1][k+1],
                                        dp[i+1][j][k+1],
                                        dp[i+1][j+1][k]);
        }
    }
}

---

전체 풀이 코드는 다음과 같다.

#include <iostream>
using namespace std;

#define MAXL 101

char str1[MAXL];
char str2[MAXL];
char str3[MAXL];

int dp[MAXL][MAXL][MAXL];

inline int max(int a, int b) { return (a > b) ? a : b; }

inline int max(int a, int b, int c) { return max(max(a, b), c); }

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

	cin >> str1 >> str2 >> str3;

	int i, j, k;
	for(i=0; str1[i]!='\0'; i++) {
		for(j=0; str2[j]!='\0'; j++) {
			for(k=0; str3[k]!='\0'; k++) {
				if(str1[i] == str2[j] && str2[j] == str3[k])
					dp[i+1][j+1][k+1] = dp[i][j][k] + 1;
				else
					dp[i+1][j+1][k+1] = max(dp[i][j+1][k+1],
											dp[i+1][j][k+1],
											dp[i+1][j+1][k]);
			}
		}
	}

	cout << dp[i][j][k] << '\n';

	return 0;
}