백준 9251번 :LCS

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

9251번: LCS

 이 문제는 다이나믹 프로그래밍으로 푸는 것이다.

라고 생각해서 접근했지만 후...모르겠어서 다른 글을 참고했다..

풀이는 말그대로 다이나믹 프로그래밍으로 푸는 것이다

두 문자열

ACAYKP

CAPCAK

가 있다고 하였을 때,

맨 처음 부분 문자열 A,AC,ACA... 와 C,CA,CAP.. 로 비교해가면서 푸는 것이다. 즉 부분 집합에서 최적해를 찾아가는 방식이다.( 라고 말은하지만 생각이 들기 어려웠고 푸는 방법은 더욱더 안떠올랐다...)

 

풀이 방법은

1)문자 값이 같으면 좌대각 값+1   

이유는 좌대각이 부분순열에 영향을 안받는 값이고 같으면 거기서 +1을 한다.

밑에 테이블을 보고 생각을 하면 ACA와 CA에서 값은  좌대각 AC와 C에서 구한 값에다가 뒤에 더해지는 A가 값이 겹치므로+1 이 된다. 

 

2)문자 값이 다르면 MAX(위쪽 값,왼쪽 값) 이다.

이유는 간단하게 문자 값이 다르므로 부분수열 수에 영향을 미치지 않는다 .

즉) ACAY 와 CA에서 값은 ACA와 CA 또는 ACAY와 C에서  가장 큰 값을 그대로 사용하면 된다. 

그리고 

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P
C
A
K

위의 테이블에서 보듯이 원래는 각 테두리에 0을 넣으면 구현하기 편하다.

계산을 끝까지 하게되면 

	A	C	A	Y	K	P
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

즉 이 예의 답은 4이다.

코드를 보자

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
string s1;
string s2;
int arr[1002][1002];
int main(){
    cin >>s1;
    cin>>s2;
    int len1=s1.size();
    int len2=s2.size();
    for(int i=0;i<len1;i++){
        for(int k=0;k<len2;k++){
            if(s1[i]==s2[k]){
                arr[i+1][k+1]=arr[i][k]+1;       //같으면 좌대각 에서 +1 
            }else{
                arr[i+1][k+1]=max(arr[i][k+1],arr[i+1][k]); //다르면 왼쪽이랑 위쪽중에 큰 값 채우기
            }
        }
    }
    cout <<arr[len1][len2];
}