[C++][백준][9252] LCS 2 (DP)

🍋 문제링크

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

9252번: LCS 2

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 6004 KB

시간 : 4 ms

🍉 Code

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

std::vector<std::vector<int> > dp;
std::vector<char> answer;
std::string str1, str2;

void preset()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

void init(){
	std::cin >> str1 >> str2;
	dp.resize(str1.length()+1, std::vector<int>(str2.length()+1,0));
}

void solution(){
	//fill dp
	for (int i = 1 ; i <= str1.length() ; i++){
		for(int j = 1 ; j<= str2.length() ; j++){
			if (str1[i-1] == str2[j-1])
				dp[i][j] = dp[i-1][j-1] + 1;
			else
				dp[i][j] = std::max(dp[i-1][j], dp[i][j-1]);
		}
	}
	//fill answer
	int k = str1.length();
	for(int j = str2.length(); j>=0 ; j--){
		if (dp[i][j] == 0)
			break;
		for (int i = k; i>=0 ; i--){
			if (dp[i][j] == dp[i][j-1])
				break;
			else if (dp[i][j] == dp[i-1][j])
				continue;
			else{
				answer.push_back(str1[i-1]);
				k = i-1;
				break;	
			}
		}
	}
}

void output(){
	std::cout << answer.size() << std::endl;
	while(!answer.empty()){
		std::cout << answer.back();
		answer.pop_back();
	}
	std::cout << std::endl;
}

int main(){
	preset();
	init();
	solution();
	output();
	return (0);
}

🥝 메모

CAPCAK ACAYKP

CAPCAK 
ACAYKP

아래 그림은 위의 순서로 입력됬다는 가능하에 그려짐

<2차원 vector 선언 및 초기화>

std::vector<std::vector<int> > dp;
dp.resize(str1.length()+1, std::vector<int>(str2.length()+1,0));

→ 2차원 벡터를 선언해 가로 str2.length, 세로 str1.length 만큼을 모두 0으로 초기화함

<C++ 입출력 객채를 가속시키는 법>

void preset()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

→ cin, cout이 scanf, printf에 비해서 속도가 많이 느리고 std::endl보다 '\n'가 훨씬 빠르다.

→ sync_with_stdio(false); 를 이용해서  C++ 입출력 객채를 가속시켜서 사용할 것이라면,

1. scanf와 printf와 섞어서 사용하지 말 것!

2. 싱글 쓰레드 환경에서만 사용할 것!

3. 그래도 시간초과가 난다면 C 표준입출력 함수들을 사용할 것!

🍓 참조

C/C++ 입출력 방법에 따른 속도 정리