백준 9251번 (C++)

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

9251번: LCS

1. 문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

 

2. 입력 / 출력

 가. 입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

 나. 출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

3. 알고리즘

LCS 문제를 이번에 처음 접하게 되었는데 도저히 감이 잡히지 않아서 LCS 문제를 해결하는 방법을 검색해보았다.

https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전

여기에 LCS(최장 공통 부분 수열)에 대해 잘 정리돼 있으니 한 번씩 읽어 보면 좋을 듯하다.

 

LCS 문제를 푸는 방법을 적용해서 이번 문제를 풀면 다음과 같이 나온다. 역추적 방법을 사용하였다.

마지막 그림의 초록색 화살표가 역추적 경로이다.

• 문자열을 배열로 입력받는다.
• 첫 번째 문자열을 s1, 두 번째 문자열을 s2라고 하면 다음과 같은 조건에 따라 배열 array를 채운다.

  1. 만약 s1[i] == s2[j] 라면, array[i+2][j+2] = array[i+1][j+1] + 1이다. 2. 그렇지 않으면, array[i+2][j+2]는 s1[i]와 s2[j] 중에 큰 값을 그 값으로 갖는다.

• s1의 길이를 N, s2의 길이를 M이라고 하면, LCS의 길이는 array[N+1][M+1]의 값이 된다.

 

4. 전체 코드

#include <stdio.h>
#define _CRT_SECURE_NO_WARNINGS
#include <string.h>
 
int main() {
    int i, j, array[1003][1003] = { 0 } , ss1, ss2, result;
    char s1[1001], s2[1001];
 
    scanf("%s\n%s", s1, s2);
    ss1 = strlen(s1);
    ss2 = strlen(s2);
 
    for (i = 0; i < ss1; i++) {
        for (j = 0; j < ss2; j++) {
            if (s1[i] == s2[j]) {
                array[i + 2][j + 2] = array[i + 1][j + 1] + 1;
            }
            else {
                array[i + 2][j + 2] = (s1[i] >= s2[j]) ? array[i + 1][j + 2] : array[i + 2][j + 1];
            }
        }
    }
 
    result = array[ss1 + 2][ss2 + 2];
    printf("%d\n", result);
}

 

5. 코드 세부 설명

for (i = 0; i < ss1; i++) {
    for (j = 0; j < ss2; j++) {
        if (s1[i] == s2[j]) {
            array[i + 2][j + 2] = array[i + 1][j + 1] + 1;
        }
        else {
            array[i + 2][j + 2] = (s1[i] >= s2[j]) ? array[i + 1][j + 2] : array[i + 2][j + 1];
        }
    }
}

알고리즘 설명할 때 이야기 것을 조건문으로 풀어내 보았다. s1[i]와 s2[j]가 같을 때/같지 않을 때로 나누어서 문제를 풀었다.