본문 바로가기

다이나믹 프로그래밍

BOJ)1562 계단 수 문제: icpc.me/1562 N자리 계단수의 개수를 구하는 문제이다. 단 조건이 추가됬는데 0~9까지 모든 수가 등장했는지 확인을 해줘야 하기 때문에 비트마스킹을 통하여 상태를 체크해주면 된다. dp테이블의 정의는 dp[pos][val][state] 일때 pos자리 수이고 val번째 수로 시작하는 state(켜진 비트에 따라 i번째 자리수가 사용됬는지)의 경우의 수이다. 점화식은 dp[pos][val][state]=dp[pos-1][val+1][state|(1 더보기
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)1576 DNA점수 문제: icpc.me/1576 점수판을 채우는 규칙이 주어질 때 주어진 DNA 문자열의 각 문자열에서 얻을 수 있는 점수의 평균의 최댓값을 구하는 문제이다. 우리는 평균의 최댓값을 구하기 위해서 총점의 최댓값을 구하면 된다. 결국 총점이 최대가 되도록 점수판을 채우면 되는것이다. 우리는 다이나믹 프로그래밍을 이용해서 총점이 최대가 되도록 점수판을 채워나갈 것이다. 점수판을 채우는 순서는 임의로 지정해 줄 수 있다. dp테이블은 dp[4][4][10*16*2] 이 될것이다. dp 테이블이 의미하는 바는 dp[x][y][z]일때 (x,y)까지 채웠고 점수판의 점수 총합이 z일 때 총점의 최댓값으로 정의하면 된다. 우리는 점수판의 총점이 음수가 될 때도 있으니 그걸 고려하여 10*16의 총점에 2를 곱해주었다.. 더보기
BOJ)10265 MT 문제: icpc.me/10265 K이하의 사람이 버스에 탈 수 있을 때 버스에 탈 수 있는 최대 인원을 출력하는 문제이다. 문제에는 조건이 있는데 A라는 사람은 B라는 사람이 버스에 안타면 A도 반드시 안타는 정보 N개가 주어진다. 우리는 이러한 조건을 B->A라는 방향 그래프로 만들어 준 SCC끼리 분류를 한다음 다음 위상 정렬을 이용하여 X라는 정점이 방문 가능한 모든점 Y는 반드시 X의 인원을 포함한다고 정의 가능하다. 이 때 X의 인원은 SCC의 그룹 크기와 동치가 된다. 따라서 연결 그래프마다 최소 인원~최대 인원 셋을 저장한 뒤 Knapsack문제를 해결하듯이 다이나믹 프로그래밍을 이용해주어 답을 계산해주면 된다. 이때 연결 그래프의 수는 SCC 그래프의 indegree가 0인 SCC의 개수이.. 더보기
BOJ)11983 Radio Contact 문제: icpc.me/11983 파머존과 소가 움직이는 경로가 주어질 때 파머존만 움직이거나 소만 움직이거나 둘이 동시에 움직일수 있다. 이동 후 둘의 거리의 제곱에 비례하게 라디오의 에너지가 소모될 때 파머존과 소가 목적지에 도착했을 때 소모된 라디오 에너지의 최솟값을 출력하는 문제이다. 우리는 이 문제를 다이나믹 프로그래밍을 통하여 해결할 수 있다. dp[x][y]의 정의는 Farmer John이 X번 이동한 위치이고 소가 Y번 이동한 위치일 때까지 소모된 라디오 에너지의 최솟값이다. 점화식은 dp[x][y]=min(dp[x-1][y],dp[x][y-1],dp[x-1][y-1])+dist(FJx ,COWy)가 되겠다. 파머존과 소가 한번도 움직이지 않았을 때는 에너지 소모가 없다고 하니 기저는 dp[.. 더보기
BOJ)2775 부녀회장이 될테야 문제: icpc.me/2775 a층 b호에 사는 주민은 a-1층의 1~b호까지의 주민의 합일때 k층n호에 사는 주민의 수를 출력하는 문제이다. 사실 k와 n의 범위가 매우 작기 때문에 그때 그때 구해줘도 TLE를 받을일은 없을것 같지만 우리는 배운 사람들이니까 다이나믹 프로그래밍을 통하여 쉽게 답을 구 할수 있다. 점화식은 dp[i][j]=dp[i-1][j]+dp[i][j-1] 이다. 12345678910111213141516171819#include #include using namespace std;int dp[15][15], t, k, n;int main() { for (int i = 1; i 더보기
BOJ)9184 신나는 함수 실행 문제: icpc.me/9184 문제에서 점화식 기저 까지 다 정해주는 진정한 꿀문제가 아닐까 싶다. 당연하게도 그냥 함수를 매번 계산한다면 시간초과가 난다. 하지만 우리는 점화식과 기저를 알고 있으니 이걸 이용해 다이나믹 프로그래밍을 이용하여 계산할때마다 결과를 배열에 저장해주면 된다. 문제에서 하라는대로 하면 쉽게 풀 수 있는 문제이다. 1234567891011121314151617181920212223242526#include #include #include using namespace std;int dp[21][21][21];int a, b, c;int func(int x, int y, int z) { if (x 20) return func(20, 20, 20); int &ret = dp[x][y].. 더보기
BOJ)14168 Cow Checklist 문제:icpc.me/14168 H의 순서와 G의 순서를 지키면서 순서대로 순회 할 때 소모되는 에너지의 최솟값을 구하는 문제이다. 이때 조건이 반드시 시작과 끝은 H의 처음과 끝이어야 한다는거다. H순서와 G순서를 각각 배열에 저장 한 뒤 다이나믹 프로그래밍을 통하여 문제를 해결하였다. dp[h][g][s]의 정의는 H순서를 h까지 G순서를 g까지 처리하고 s가 1이면 H의 h번째 점에 서 있을 경우 s가 0이면 G의 g번째 점에 서 있을 경우앞으로 순회하는데 소모되는 에너지의 최솟값이다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include #include #define INF 9876543.. 더보기
BOJ)2401 최대 문자열 붙여넣기 문제 : icpc.me/2401 긴 문자열에 여러개의 짧은 문자열을 붙일 때 얼마만큼 붙일 수 있는지 최대 길이를 출력하는 문제이다. KMP로 긴문자열에 대응하는 짧은 문자열들을 찾아주어 (a부터b까지 짧은 문자열이 같다면) a 점에서 붙일 수 있는 점들을 vt[a]에 b로 저장 해 준 후 다이나믹 프로그래밍을 이용하여 답을 구해준다 . dp테이블의 정의는 dp[x]는 x번째 문자열부터 시작하였을 때 붙일 수 있는 문자열의 최대 길이이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include #inc.. 더보기