본문 바로가기

다이나믹 프로그래밍

BOJ)2157 여행 문제: icpc.me/2157 번호가 증가하는 순서대로만 여행을 할 때 1번 도시에서 N번 도시까지 항공편을 K번 이하로만 이용하여 갈 때 얻을 수 있는 기내식 점수의 최댓값을 구하는 문제다. dp[pos][val]= pos번 나라까지 여행하고 항공편을 val번 이용했을 때 얻을 수 있는 최대 기내식 점수 로 정의 한 뒤 문제를 해결하면 된다. 소스코드는 탑 다운 방식으로 구현하여 테이블의 정의가 반대다. 123456789101112131415161718192021222324252627#include #include #include #define INF 987654321using namespace std;int a[301][301], n, m, k, dp[301][301], x, y, z;int func.. 더보기
BOJ)2618 경찰차 문제:icpc.me/2618 경찰차 두대가 사건을 순서대로 처리할 때 가장 적은 거리를 이동하도록 사건을 배치하는 경우와 거리를 출력하는 문제이다. dp[x][y] = 경찰차 1이 x번째 사건을 경찰차 2가 y번째 사건을 마지막으로 처리하였을 때 이동한 거리의 합의 최솟값으로 정의한 뒤 문제를 해결해주면 된다. 점화식은 dp[x][y] = min(dp[prev][y]+ dist(prev,x) , dp[x][prev] + dist(prev,y))이다. 소스에서는 바텀업 방식으로 구현하여 테이블의 정의가 약간 바뀌었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#in.. 더보기
BOJ)2688 줄어들지 않아 문제: icpc.me/2688 N자리 줄어들지 않는 숫자를 구하는 문제이다. dp테이블을 dp[pos][val]을 val로 끝나는 pos자리 줄어들지 않는 숫자의 수로 정의한 뒤 다이나믹 프로그래밍을 통하여 해결할 수 있다. long long을 사용하지 않는다면 overflow가 발생할 수 있다. 12345678910111213141516171819202122232425262728#include #include #include using namespace std;typedef long long ll;ll t, dp[100][10], n;ll func(ll pos,ll val) { if (val 9)return 0; if (pos == 1)return 1; ll &ret = dp[pos][val]; if .. 더보기
BOJ)1520 내리막 길 문제:icpc.me/1520 지도에서 자기보다 숫자가 낮은 곳으로 이동할 수 있을 때 0,0에서 n-1 ,m-1로 갈 수 있는 경로의 개수를 출력하는 문제이다. 우리는 다이나믹 프로그래밍을 이용하여 문제를 해결할 수 있다. dp[x][y]는 0,0에서 x,y로 이동할 수 있는 경로의 수라고 정의한 뒤 4방향 탐색으로 테이블을 채워나가면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;int dx[] = { 0,0,-1,1 };int dy[] = { -1,1,0,0 };int n, m;int chk(int x, int y) { return 0 더보기
BOJ)10422 괄호 문제: icpc.me/10422 괄호 문자열이 되려면 괄호 문자열이 채워져 나가는 과정에서 )의 개수가 (개수보다 많으면 안된다. 이를 만족하면서 채워져 나가는 길이가 N인 괄호문자열의 개수를 다이나믹 프로그래밍을 이용하여 구해주면 된다. N이 홀수인 경우 0을 출력하고 N이 짝수인 경우 dp[n/2][n/2]를 출력하면 된다. dp[x][y]의 정의는 (가 x개 )가 y개 까지 그려진 괄호문자열의 개수 이다. 점화식은 dp[x][y]=dp[x-1][y]+dp[x][y-1]이 된다. 123456789101112131415161718192021222324252627282930#include #include #include #define MOD 1000000007typedef long long ll;usin.. 더보기
BOJ)10835 카드게임 문제: icpc.me/10835 오른쪽 카드를 버릴 때 점수를 얻을 수 있을 때 얻을 수 있는 최고 점수를 구하는 문제이다, dp[x][y] b[y]) dp[x][y]=max(dp[x][y],dp[x][y+1]+b[y]) 라는 점화식을 통하여 문제를 해결할 수 있다. 12345678910111213141516171819202122232425#include #include #include #define INF 987654321using namespace std;int dp[2001][2001], n, a[2001], b[2001];int func(int x, int y) { if (x == n || y == n)return 0; int &ret = dp[x][y]; if (ret != -1)return r.. 더보기
BOJ)1890 점프 문제: icpc.me/1890 규칙에 맞게 갈 수 있는 경로가 주어질 때 오른쪽 맨 아래로 가는 경우의 수를 계산해주는 문제이다. 우리는 dp[x][y] = 0,0에서 x,y로 가는 경우의 수로 테이블을 잡아 준 뒤 x,y에서 나보다 x좌표나 y좌표가 작은 지역중 나에게로 올 수 있는 경우의 수를 더해줘서 n^3 다이나믹 프로그래밍으로 구해줄 수 있다. 1234567891011121314151617181920212223242526272829#include #include #include using namespace std;typedef long long ll;ll n, dp[101][101], a[101][101];ll func(int x, int y) { if (x == y&&y == 0)return .. 더보기
BOJ)2916 자와 각도기 문제:icpc.me/2916 만들 수 있는 각도들이 주어질 때 그 각도들을 더하거나 빼서 만들 수 있는 모든 각도를 구하는 문제이다. 다이나믹 프로그래밍을 통하여 dp[pos][val] = pos번째 각도 까지 이용하여 구할 수 있는 val(각도)로 구해주면 된다. 123456789101112131415161718192021222324252627#include #include using namespace std;int n, k;int a[11], dp[361][11], q[11], r[361];void func(int val, int pos) { if (pos == n)return; if (dp[val][pos])return; dp[val][pos] = true; r[val] = true; int nex.. 더보기
BOJ)12019 동아리방 청소! 문제:icpc.me/12019 동아리방에 사람들이 들어올때마다 더러움이 누적되고 사람들은 더러움만큼 불쾌함을 느끼게 될 때 N일동안 딱 M번만 청소가 가능하다. N일 동안 들어온 사람 수가 주어질 때 사람들이 느끼는 총 불쾌함의 최솟값을 구하는 문제이다. 우리는 다이나믹 프로그래밍을 통하여 답을 구해줄 수 있다. 근데 불쾌함을 계산할때 (그날 들어온 사람 수) x (누적 된 더러움) 이므로 더러움을 날마다 들어오는 사람들의 수의 psum을 통하여 관리해준다. 그리고 psum으로 누적 된 더러움을 계산할 때 그날까지의 psum - 청소한 날의 psum으로 계산해줘야 하기 때문에 dp테이블에 마지막으로 청소한날을 가지고 가야한다. 따라서 dp 테이블은 dp[pos][state][last] 가 되며 의미는 p.. 더보기
BOJ)2262 토너먼트 만들기 문제:icpc.me/2262 선수들의 토너먼트를 만들 때 매 시합마다 두 선수의 랭킹 차이의 총 합의 최솟값을 구하는 문제다. (x,y)의 토너먼트 그룹과 (z,w)의 토너먼트 그룹이 붙게되었을 때 랭킹 차는 abs(min(x~y)-min(z,w))이므로 이 식을 이용하여 점화식을 짜주면 된다. dp[lo][hi]의 정의는 lo부터 hi까지의 토너먼트를 만들 때 랭킹차의 총합의 최솟값이다. 점화식은 dp[lo][hi]= (i = lo~hi-1) min(dp[lo][i]+dp[i+1][hi]+abs(min(lo~i)-min(i+1~hi))) 이다. 1234567891011121314151617181920212223242526272829303132#include #include #include #define.. 더보기