1R/2016 09 17

오늘의 문제

• 2

참가자

• 박인서

코드

15이원준

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
using namespace std;
char f[1010] = {0,}, s[1010] = {0,},ans[1010] = {0,};
int len[1010][1010] = { 0, };

int main(){
  cin>> f >> s;
  int x, y;
  x = strlen(f);
  y = strlen(s);
  for(int i = 1; i<=x; i++){
    for(int j = 1; j<=y; j++){
      if(f[i-1] == s[j-1]){
        len[i][j] = len[i-1][j-1] + 1;
      }
      else{
        len[i][j] = max(len[i-1][j], len[i][j-1]);
      }
    }
  }
  int num = len[x][y];
  cout<<num<<endl;
  ans[num] = '\0';
	num--;
	int i = x, j = y;
	while (i >= 1 && j >= 1 && num >= 0) {
		if (f[i-1] == s[j - 1]) {
			//cout<< ">";
			//cout<< i << " " << j << endl;
			ans[num] = f[i - 1];
			num--;
			i--;
			j--;
		}
		else {
			//cout<< i << " " << j << endl;
			if (len[i - 1][j] >= len[i][j - 1]) {
				i--;
			}
			else {
				j--;
			}
		}

	}
	cout << ans << endl;
}

박인서

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

int lcs[1001][1001] = { 0, };
char len1[1001] = { 0, }, len2[1001] = { 0, };

int main()
{
	//입력
	std::cin >> len1 >> len2;
	
	//lcs 탐색
	int n = strlen(len1), m = strlen(len2);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (len1[i - 1] == len2[j - 1])
				lcs[i][j] = lcs[i - 1][j - 1] + 1;
			else
				lcs[i][j] = std::max(lcs[i][j - 1], lcs[i - 1][j]);
		}
	}

	//lcs 길이 출력
	std::cout << lcs[n][m] << std::endl;
	std::vector<char> res;
	int x = n - 1, y = m - 1;
	
	//경로 되추적
	while (x >= 0 && y >= 0)
	{
		if (len1[x] == len2[y]) {
			res.push_back(len1[x]);
			x--, y--;
		}
		else lcs[x + 1][y] >= lcs[x][y + 1] ? y-- : x--;
	}
	
	//lcs 출력
	std::reverse(res.begin(), res.end());
	for (int i = 0; i < res.size(); i++) std::cout << res[i];
	
	return 0;
}

아이디어

박인서

• 설명으로 대신합니다.