본문 바로가기

다이나믹 프로그래밍

BOJ)2300 기지국 문제: icpc.me/2300 모든 건물을 커버하는 기지국들을 세울 때 기지국의 설치비용의 최솟값을 구하는 문제이다. n이 10000이고 시간 제한이 2초이기 때문에 n^2 dp를 생각해볼 수 있다. dp[i]= MIN[for(j: 0~i-1) : dp[j]+max(wide[i]-wide[j-1],2*maxheight) ] 라는 점화식이 나온다. 1234567891011121314151617181920212223242526#include #include using namespace std;typedef long long ll;ll n, dp[10010];pair a[10010];int main() { scanf("%lld", &n); for (int i = 1; i 더보기
BOJ)11985 오렌지 출하 문제: icpc.me/11985 오렌지를 연속적으로 M개 이하 씩 포장할 때 포장비용이 주어질 때 전체를 포장했을 때 포장비용의 최솟값을 출력하는 문제이다. 이 문제는 다이나믹 프로그래밍으로 해결할 수 있다, DP[i]= i까지 포장하는데 필요한 최소 비용 이라고 생각하면 for( j= i-m+1~i)에 대해서 MIN(dp[j-1]+k+(i-j+1)*(max(i~j)-min(i~j))가 된다. 123456789101112131415161718192021#include #include using namespace std;typedef long long ll;ll n, m, k, dp[20020], a[20020];int main() { scanf("%lld%lld%lld", &n, &m, &k); for .. 더보기
BOJ)9023 연습시즌 문제: icpc.me/9023 연습 일정에 맞춰서 경기장이나 호텔을 빌려야 할 때 두 팀이 지불해야하는 비용의 합의 최솟값을 구하는 문제이다. 다이나믹 프로그래밍을 이용하여 해결해줄 수 있는데 점화식을 세울 때 주의할 점은 두 팀 다 쉬는날이 없게해야한다. (무조건 손해) dp테이블을 dp[x][y][bx][by] (x번째 경기 y번째 경기를 진행해야되고 bx,by는 이전에 호텔에 묶었는지 여부 )로 세워준다음에 점화식을 세워주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #include #include #define INF 1e9using nam.. 더보기
BOJ)2507 공주 구하기 문제: icpc.me/2507 0에서 n-1을 갔다가 0으로 다시 돌아와야하는 bitonic tour의 변형문제이다. 바이토닉 투어는 다이나믹 프로그래밍으로 해결해줄 수 있다. dp[x][y] = 올 때 x번 정점을 밟고 갈 때 y번 정점을 밟을 때의 경로의 개수 점화식은 중복을 제거해주기 위해 max(x,y)보다 큰 섬으로만 보낼 수 있어야 한다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include using namespace std;int n, w[505], g[505], b[505], a[505][505], dp[505][505];const int MOD = 1000;int func(in.. 더보기
BOJ)12869 뮤탈리스크 문제:icpc.me/12869 3개의 SCV의 체력이 주어질 때 뮤탈리스크가 각 SCV를 서로 다른 공격으로 공격할 때 공격횟수의 최솟값을 출력하는 문제이다. 이 문제는 그리디하게 힘들다고 생각한 순간 동적 계획법을 떠올릴 수 있다. 하지만 공격횟수로 테이블을 잡기 애매하기 때문에 각 SCV의 체력에 포커스를 맞춘다면 dp[x][y][z] = 체력이 x , y ,z 인 SCV를 파괴하는데 필요한 최소 공격 횟수로 테이블을 세울 수 있고 점화식은 공격가능한 6가지 방법 중에 최솟값을 호출하면 된다. 123456789101112131415161718192021222324252627#include #include #include #define INF 987654321using namespace std;int .. 더보기
SPOJ)BATMAN2 문제:http://www.spoj.com/problems/BAT2/ 각 방의 가중치가 주어지고 두명의 사람이 이동을 한다. 한 사람은 1에서 부터 다른 한사람은 N에서 부터 이동할 때 겹치지 않는 경로로 가중치가 증가하는 순서대로 이동할 때 밟을 수 있는 방의 수의 최댓값을 출력하는 문제이다. 다이나믹 프로그래밍을 이용하여 dp[pos][x][y]의 정의를 1번부터 pos번 정점까지 확인 했을 때 한 사람은 x번 정점을 마지막으로 한사람은 y번 정점을 마지막으로 밟았다고 생각하면 점화식을 세울 수 있다. dp[pos][x][y]= max(dp[pos][a[pos]][y]+1, dp[pos][x][a[pos]]+1 , dp[pos][x][y]) 1234567891011121314151617181920212.. 더보기
BOJ)12995 트리나라 문제: icpc.me/12995 트리가 주어질 때 노드가 K개인 서브트리의 개수를 구하는 문제이다. 트리DP임을 인지하고 dp[pos][state] = tr[pos].size()) return state == 1 ? 1 : 0; ll &ret = dp[pos][idx][state]; if (ret != -1)return ret; ret = 0; for (int i = 0; i 더보기
BOJ)14501 퇴사 문제: icpc.me/14501 i일 부터 일을 할 때 얻을 수 있는 급여의 최댓값으로 DP테이블을 잡으면 쉽게 계산할 수 있는 문제이다. dp[i]의 점화식은 max(dp[i+1],dp[i+t[i])+p[i]) 가 된다. 1234567891011121314151617181920#include #include #include using namespace std;int n, dp[16], t[16], p[16];int func(int pos) { if (pos == n + 1)return 0; if (pos > n + 1)return -987654321; int &ret = dp[pos]; if (ret != -1)return ret; return ret = max(func(pos + 1), func(po.. 더보기
BOJ)2213 트리의 독립집합 문제: icpc.me/2213 트리에서 각 정점에 대한 가중치가 주어지고 정점들의 가중치를 최대로 가지는 최대독립집합 set을 구하는 문제이다. 트리에서의 최대 독립집합을 구하는 문제이기 때문에 사이클이 존재하지 않으므로 다이나믹 프로그래밍으로 해결할 수 있다. dp[pos][state]로 pos번째 정점에 대한 선택여부를 state로 강제한다면 점화식을 쉽게 세워줄 수 있다. 해당 정점을 선택할 경우 해당 정점에 대한 가중치를 얻고 자식들은 state를 선택안함으로 강제된다. 해당 정점을 선택하지 않을 경우 자식들의 state 결과는 선택하거나 선택안하는 경우 중 최댓값을 가지게 된다. 두 케이스에 따라 점화식을 다르게 세워준 후 다이나믹 프로그래밍을 이용하여 답을 구해준 뒤 역추적을 해주면 된다. 1.. 더보기
BOJ)7579 앱 문제: icpc.me/7579 최소한의 비용을 사용하여 m만큼의 메모리를 얻을 때 비용을 출력하는 문제이다. dp[pos][cost]= pos번째 앱까지 cost만큼의 비용을 사용해 얻을 수 있는 메모리의 최댓값으로 정의 한 뒤 파라메트릭 서치를 이용하여 cost값을 조정해주면 된다. 12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std;int n, cost, m[101], c[101], dp[101][10001];int func(int pos, int cos) { if (pos = 0) ret = max(ret, func(pos - 1, cos - c[pos]) + m.. 더보기