Skip to content

BOJ-9252-LCS 2 #67

Open
Open

Description

@changicho

9252. LCS 2

링크

난이도 정답률(_%)
Gold V 42.193

설계

동적 계획법

정리

내 코드 (ms) 빠른 코드 (ms)
652

고생한 점

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

#define MAXSIZE 1001
#define nl "\n"


using namespace std;

int DP[MAXSIZE][MAXSIZE];
string LCS[MAXSIZE][MAXSIZE];

void solution() {
	string A, B;

	cin >> A >> B;

	int A_Size = A.length();
	int B_Size = B.length();

	for (int i = 1; i <= A_Size; i++) {
		for (int j = 1; j <= B_Size; j++) {
			if (A[i - 1] == B[j - 1]) {
				DP[i][j] = DP[i - 1][j - 1] + 1;
				LCS[i][j] = LCS[i][j] + LCS[i - 1][j - 1] + A[i - 1];
			}
			else {
				DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);

				if (LCS[i - 1][j].length() > LCS[i][j - 1].length()) {
					LCS[i][j] = LCS[i - 1][j];
				}
				else {
					LCS[i][j] = LCS[i][j - 1];
				}
			}

		}
	}

	cout << DP[A_Size][B_Size] << nl << LCS[A_Size][B_Size] << nl;
}

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

	solution();

	return 0;
}

Activity

  1. added this to the day9 milestone on Jan 16, 2020
  2. added
    questionFurther information is requested
    and removed
    not clear진행중인 코드
    on Jan 16, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    clear정답코드questionFurther information is requested

    Projects

    No projects

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions