뜌릅

LCS문제 입니다. 저는 처음 봤는데, 구글링을 해본 결과, 유명한 문제 유형이더군요. 이 문제도 전에 풀었던 Knapsack문제와 매우 유사하게 풀었습니다. 역시 dp를 사용했습니다. Dp문제는 너무 어려운 것 같습니다. 보고나면, 쉬운데 발상 자체는 떠올리기가 힘듭니다. 이 문제를 풀기위해서는 한글자씩 비교하면서, 맞으면 갯수+1를 해야 합니다. 하지만, 단순히 모든걸 비교하면, 시간초과가 발생합니다. 결국에는 어떤 방식으로 비교하는 문제가 되는 겁니다. 이 문제는 BFS같은 느낌으로 풀었습니다. 둘이 비교해서 같으면 +1, 다르면 첫번째 문자열만 다음 문자로 넘긴것과 두번째 문자열만 다음 문자로 넘겼을 경우를 비교하여, 둘중 최댓값을 출력하는 겁니다. #import using namespace st..

백준에서 The Triangle문제를 풀어보았습니다. 처음에는 실버2난이도여서, 대충 recursive algorithm으로 풀려고 했으나, 시간을 초과했고, 이후 dp문제임을 깨닫고 dp를 사용하여 풀어보았습니다. 처음 보는순간 recursive algorithm을 이용한 dfs이면 풀수 있지 않을까?? 라는 생각이 먼저 들었습니다. dfs()함수를 새로 만들어서, 왼쪽으로 간경우와 오른쪽으로 간경우를 호출하고, 그 둘의 값을 비교하여 더 큰값을 return시키는 함수를 만들었습니다... int n; vector v[500]; int dfs(int i,int floor){ if(floor >n; rep(i,n){ int a; int j =i+1; while(j--) { cin >> a; v[i].pb(..