본문 바로가기

다이나믹 프로그래밍

BOJ)11964 Fruit Feast 문제: icpc.me/11964 최대 포만감의 최대치가 t이고, 오렌지를 먹으면 a만큼 레몬을 먹으면 b만큼 포만감이 오를 때, 최대 포만감을 구하는 문제이다. 단, 조건이 하나 있는데 딱 한번 물을 마시면 현재 포만감을 반으로 줄일 수 있다. 현재 물을 마셨는 지 아닌지를 제약조건으로 둔다면 다이나믹 프로그래밍으로 문제를 해결할 수 있다. dp[i][j]= 포만감이 i이고 제약조건(물을 마셨는 지 여부)이 j일 때 상태의 존재 여부 12345678910111213141516171819202122232425#include #include #include using namespace std;int dp[5000005][2];int t,a,b,r;int main(){ scanf("%d%d%d",&t,&a,&.. 더보기
BOJ)15673 헤븐스 키친2 문제 :http://icpc.me/15673 n개의 수열이 주어질 때, 연속 된 두 구간을 선정을 한다. 두 구간을 a,b라하면 구간 a의 합과 구간 b의 합의 곱의 최댓값을 구하는 문제이다. 생각해보면 구간 a의 합과 구간 b의 합의 최솟값들을 곱하는 경우와, 구간 a의 합과 구간 b의 합의 최댓값들을 곱하는 경우가 답의 후보가 됨을 알 수 있다. 구간 a가 i~j 구간 b가 k~l 이라고 해보자. k를 고정시킨 뒤 생각해보면 구간 k~l의 합은 psum[l]-psum[k-1]이므로, k보다 크거나 같은 범위의 psum의 최댓값과 최솟값을 가지고 있으면, 구간 b의 최댓값과 최솟값을 구할 수 있다. 그럼 i~j 구간의 최댓값과 최솟값은 어떻게 처리할 수 있을까? 구간 i~j의 합은 psum[j]-psu.. 더보기
BOJ)1856 단어 게임 문제: icpc.me/1856 w개의 문자열이 주어진다.길이 l의 문자열을 앞서 주어진 w개의 문자열로만 표현하고 싶을 때 지워야하는 문자의 최소 개수를 출력하는 문제이다.dp[x]=길의 l의 문자열을 길이 x까지 봤을 때 지워야하는 최소 문자의 수로 정의한 뒤 점화식을 세우면dp[x]를 채우기 위해선 w개의 각각의 문자열에 대해서 저 문자를 남기기 위하여 지워야할 개수를 구해주면 l*l*w의 시간복잡도로 디피 테이블을 채울 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include #include using namespace std;int w,l,dp[333];st.. 더보기
BOJ)13330 유사 팰린드롬 문제: icpc.me/13330 w를 구성할 수 있는 세타 팰린드롬의 최소 개수를 출력하는 문제이다. 이 문제를 해결하기 위하여 두가지 디피 테이블을 정의해야한다. dp1[l][r]은 l,r 구간의 u의 개수 dp2[pos]는 0~pos 의 문자열을 구성 할 수 있는 세타 팰린드롬의 최소 개수라 정의하면 n^2으로 dp2를 채우기 위해 for문을 돌릴 때 이터레이터 j에 대한 검사를 dp1으로 할 수있다. 123456789101112131415161718192021222324252627282930#include #include #include using namespace std;int n, k, l, dp[10010];int a[10010][10010];char s[10010];int func(int l.. 더보기
BOJ)2337 트리 자르기 문제: icpc.me/2337 트리에서 임의의 몇개의 간선을 잘라서 크기가 m인 트리를 얻고 싶을 때 잘라야하는 간선의 최소 개수를 구하는 문제이다. 트리디피로 풀 수 있는 문제이다. 기존에는 트리 디피를 n^3의 방법으로 풀어왔지만 이번에 smu형님의 도움으로 n^2 log n으로 푸는 방법을 알게 되었다. 우선 dp테이블을 dp[here][k]를 here번 정점이 루트인 크기가 k인 트리를 만드는데 필요한 간선컷의 최솟값으로 정의하면 dp[here][k]를 어떤식으로 빌드할거냐면 here가 가지는 자식들은 여러개의 서브트리를 이룰것이다. 이 서브트리를 하나씩 병합하면서 dp[here][k]를 채울 것이다. 당연히 처음에는 dp[here][1]밖에 없을 것이다 .여기서 1은 곧 자기 자신이다 이는 0으.. 더보기
BOJ)1460 진욱이의 농장 문제: icpc.me/1460 n*n 크기의 격자에 씨를 뿌리는 방법이 주어지고 격자에서 임의의 정사각형을 선택하여 정사각형 내부의 점에 서로 다른 씨앗이 최대 2개가 되도록 정사각형을 선택할 때 가장 넓은 정사각형의 넓이를 출력하는 문제이다. 씨앗의 종류인 F의 범위가 0~7인걸 이용하여 F^2+F로 모든 경우의 씨앗을 정한다면 현재 상태에서 해당하는 씨앗이 뿌려져있는 가장 넓은 정사각형을 구하는 문제로 치환하여 풀 수 있다. 이는 다이나믹 프로그래밍을 이용하여 n^2에 해결할 수 있다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include using namespace std;int res, a[10.. 더보기
BOJ)2419 사수아탕 문제:icpc.me/2419 사탕이 담긴 사탕바구니가 x축위에 있고 1초마다 사탕 바구니의 사탕이 1개씩 사라질 때 수아가 먹을 수 있는 최대의 사탕 수를 구하는 문제이다. 문제가 다이나믹 프로그래밍임은 쉽게 알 수 있었지만 먹을 수 있는 최대의 사탕수에 포커스를 맞추니 어려워진 문제였다. 이를 dp[l][r][state]로 해결해야하는데 l에서 r까지 사탕을 커버하고 state(왼,오)에 서있을 때 먹는 최대의 사탕수라고 정의를 한 뒤 제출을 하니까 WA를 받았다. 다시 잘 생각해보니 l~r을 커버할 때 나머지 구간에 사라진 사탕수가 항상 최적으로 있을 수 없다는 걸 깨달았다. 따라서 dp테이블의 정의를 바꾸어 l에서 r까지 구간을 커버하고 사라지는 사탕 수로 문제를 풀어야한다. 근데 이 또한 사라지는.. 더보기
BOJ)10272 현상금 사냥꾼 김정은 문제:icpc.me/10272 왼쪽 부터 오른쪽으로 순회한 뒤 순회하지 않은 정점들을 오른쪽에서 왼쪽으로 다시 순회할 때 이동거리의 최솟값을 구하는 문제이다. 이 문제는 바이토닉 투어 문제이므로 N^2 다이나믹 프로그래밍으로 해결할 수 있다. 우선 바이토닉 투어 문제는 dp[x][y]라는 테이블을 세울 수 있다. 이 때 x.는 갈 때 y는 올 때 까지 커버한 정점들의 수 이다. 점화식을 세울 때 현재 x,y까지 커버했다면 다음에 커버해야 할 정점은 당연히 max(x,y)+1이 되므로 이 정점을 갈 때 커버할 지 올 때 커버할지만 결정해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include #inc.. 더보기
BOJ)1514 자물쇠 문제: icpc.me/1514 비밀번호 A를 B로 바꾸기 위한 최소 돌림의 횟수를 구하는 문제이다. 동적 계획법을 통해 문제를 해결 할 수 있다. dp[pos][x][y][z][flag]=> pos번 째 자물쇠를 볼 때 x: pos번 자물쇠를 돌린 범위 y: pos+1번 자물쇠를 돌린 범위 z:pos+2번 자물쇠를 돌린 범위(flag는 자물쇠를 돌리는 방향성) 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include using namespace std;int n, a[110], b[110], dp[110][10][10][10][2];int modulo(int x) { while (x 더보기
BOJ)5721 사탕 줍기 대회 문제: icpc.me/5721 최대로 가져갈 수 있는 사탕의 수를 구하는 문제이다. 동적 계획법으로 문제를 해결 가능하다. dp[x][y][z] = x-1행 까지 모든 사탕상자와 x행의 y행 까지의 사탕상자를 커버했을 때 가질 수 있는 최대 사탕 개수(이 때 z는 x행에서 사탕상자를 한번이라도 커버했는 지 여부이다) 이렇게 정의를 해주면 dp[x][y][z]= max(a[x][y]+ dp[x][y+2][1], dp[x][y+1][z]) 라는 대략적인 점화식이 세워진다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include using namespace std;vecto.. 더보기