전체 글 썸네일형 리스트형 BOJ)2662 기업투자 문제: icpc.me/2662 투자 가능금액과 기업의 수가 주어지고 해당 기업에 x원만큼 투자했을 때 얻을 수 있는 이득 y가 주어질 때 최대 이익을 출력하는 문제이다. 최대 이익은 다이나믹 프로그래밍을 통하여 구해줄 수 있다. 테이블 dp[val][pos]의 정의는 "val 만큼 투자 가능할 때 pos번째 기업부터 n번째 기업까지 투자하여 얻을 수 있는 최대 이익"이 될것이다. 4 점화식은 dp[val][pos] = for(i=1~k) max(dp[val-i][pos+1]+a[i][pos]) 가 될것이다. 여기서 a[x][y]는 y번째 기업에 x만원을 투자하여 얻을 수 있는 돈이다. 이 때 역추적을 해주기 위하여 최댓값의 갱신이 일어날 때 마다 역추적 배열을 갱신해준 뒤 함수 종료후 백트래킹 해주면 된.. 더보기 BOJ)9252 LCS 2 문제: icpc.me/9252 LCS를 구해주는 문제이다. 다이나믹 프로그래밍을 통하여 LCS를 구해준 뒤 백트래킹하여 해당 LCS를 출력해주면 된다. dp테이블의 정의는 dp[x][y]는 첫번째 문자열을 x까지 두번째 문자열을 y까지 봤을 때 LCS의 크기이다. 점화식은 (if a[x]!=b[y]) dp[x][y]=max(dp[x][y-1],dp[x-1][y]) else dp[x][y]=dp[x-1][y-1] 이 된다. 소스코드에서는 테이블의 정의를 반대로 사용하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include #include #include usin.. 더보기 BOJ)1701 Cubeditor 문제: icpc.me/1701 문자열이 주어질 때 2번이상 나오는 부분 문자열 중 가장 길이가 긴 부분 문자열의 길이를 출력하는 문제이다. N이 5000밖에 안되기 때문에 문자열의 모든 Suffix에 대해서 failure function을 구해준 뒤 그 중 최댓값을 출력하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #define MAX_N 5001using namespace std;char a[MAX_N][MAX_N];int l, r;vector pi;void getpi(const char *c,int len) { pi.clear(); pi.resize(len); .. 더보기 이전 1 ··· 81 82 83 84 85 86 87 ··· 118 다음