DP
백준 BOJ 2616 소형기관차
문제 백준 BOJ 2616 소형기관차 https://www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 사용 알고리즘 Dynamic programming Prefix sum 풀이 누적합 + DP. 우선 소형 기관차가 최대로 끌 수 있는 객차의 수에 해당하는 길이의 구간마다 합을 구해 놓고 2차원 DP를 돌림. dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+b[i]); dp[i][j] = i번째 객차까지 j개의 소형기관차를 썼을 때 최댓값.
백준 BOJ 5582 공통 부분 문자열
문제 백준 BOJ https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 사용 알고리즘 Dynamic programming String 풀이 2차원 DP. dp[i][j] = 첫번재 문자열 i까지, 두번째 문자열 j까지 봤을 때 최대 길이 if(s1[i]==s2[j]){ dd[i+1][j+1]=dd[i][j]+1;
백준 BOJ 10422
https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 알고리즘 : DP, 카탈란 수 일단 홀수면 무조건 0 짝수면 dp를 사용. dp[i]를 구할 때 i-2개의 괄호들은 이미 완성된 괄호들이라고 보고 가능한 모든 경우의 수를 찾아 더한다. dp[j]*dp[i-2-j] 찾아보니 카탈란 수라는 개념이었다.