[C/C++ 백준 9251번] LCS (Gold 5)

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

9251번: LCS

나름 야심차게 코드를 짜고, 예시도 잘 나와 검사해본 코드.

---

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(void){
	char a[1001];
	char b[1001];
	char usedalpha[30];
	int LSC1cnt=0, LSC2cnt=0, LSC1start=0, LSC2start, usedalphacnt=0, lsc, arrlen=0;
	scanf("%s %s",a,b);
	int alength=strlen(a);
	int blength=strlen(b);
	bool keepgo=true;
	while(LSC1start<alength){
		LSC2start=0;//얘는 이제 처음부터 찾아야댐 
		for(int i=0; i<usedalphacnt; i++){
			if(a[LSC1start]==usedalpha[usedalphacnt])//앞에 있었는지 검증 
			{	keepgo=false;	printf("fuck");}
		}
		if(keepgo==true){
			lsc=0;//이번 부분증가수열의 길이 
			usedalpha[usedalphacnt]=a[LSC1start];//usedalpha에 저장함 
			usedalphacnt++;
			LSC1cnt=LSC1start;//LSC1 시작부분 
			while(LSC1cnt<alength){//LSC1start부터 alength-1까지 돌아감  
				LSC2cnt=LSC2start;
				while(LSC2cnt<blength){
					if(a[LSC1cnt]==b[LSC2cnt]){
						lsc++;
						LSC2start=LSC2cnt+1;
						break;
					}
					LSC2cnt++;
				}
				LSC1cnt++;
			}
		}
		LSC1start++;
		arrlen=max(arrlen, lsc);
		printf("%d\n",lsc);
	}
	printf("%d",arrlen);
}

---

하지만 ABAB, AAB라는 단순한 문자열도 해결하지 못하더라. AAB가 LCS인데, 내 코드는 그냥 바로 다음글자 보이자마자 부분 수열에 집어넣어 버려서 해결하지 못한다. 

일단 다 제쳐놓고 생각하더라도, 다이나믹 프로그래밍이라는 특징을 하나도 활용하지 않았다. 배열 dp를 다시한번 생각해보자.

....모르겠어서 다른 분들의 코드를 봤다. 핵심은 다음과 같더라. 일단 dp[a][b](1번째 수열의 a번째 문자, 2번째 수열의 b번째 문자의 LCS)를 이렇게 잡고, 새로운 a+1번째 문자와 b+1번째 문자가 들어오면 다음과 같이 판단한다.

 

① 두 개가 같을 경우

 이 경우는 당연히 dp[a+1][b+1] = dp[a][b] +1

② 두 개가 다를 경우

 이 때 LCS가 새로 생긴다고 생각해보자. 두 문자가 다르기 때문에 새로 생긴 LCS에는 두 문자를 공통적으로 포함하지 않는다(그 문자랑 같은 종류의 문자가 아니라, 그 두개 문자를). 그리고 당연히 dp[a][b] >= dp[i][j] (a>=i, b>=j)이므로, 새로 들어온 문자가 LCS에 포함 되든 안되는 dp[a+1][b+1] = max(dp[a][b+1], dp[a+1][b])가 성립한다.

 

이제 코드를 짜보면,

---

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(void){
	char s1[1001], s2[1001];
	scanf("%s %s",s1,s2);
	int lens1=strlen(s1), lens2=strlen(s2);
	int s1cnt=0, s2cnt=0;
	short dp[1001][1001]={0,};
	for(s1cnt=1; s1cnt<=lens1; s1cnt++){
		for(s2cnt=1; s2cnt<=lens2; s2cnt++){
			
			if(s1[s1cnt-1]==s2[s2cnt-1])
				dp[s1cnt][s2cnt]=dp[s1cnt-1][s2cnt-1] + 1;
			else{
				dp[s1cnt][s2cnt]=max(dp[s1cnt-1][s2cnt], dp[s1cnt][s2cnt-1]);
			}
		}
	}
	printf("%d",dp[lens1][lens2]);
}

---

dp배열을 short로 만든건, 어짜피 dp내부 숫자의 크기는 커봤자 1000을 넘지 않기때문이다. int형으로 만들면 실행이 안되더라. 알고리즘만 알고 있다면 그리 어렵지 않은 문제이다.