다이나믹 프로그래밍 (6) 썸네일형 리스트형 [BOJ] 10067 수열 나누기 문제 링크: https://www.acmicpc.net/problem/10067 문제 요약음이 아닌 정수 $n$개로 이루어진 수열이 있다. 이 수열을 $k+1$개로 나누어야 하는데, 한 번 나눌 때 마다 새로 나누어진 각 부분의 원소의 합을 곱한 것 만큼의 점수를 얻을 수 있다. 이 때 얻을 수 있는 점수의 최댓값과 그 순서를 구하는 문제이다.$2 \leq n \leq 100,000$, $1 \leq k \leq \min(n-1,200)$ 이다. 풀이 과정 가장 먼저 해야 할 관찰은 어느 순서로 수열을 자르던 간에 최종적으로 얻는 점수에는 변함이 없다는 것이다. 만약 어떤 부분을 2번 잘라 3개의 수열로 나누고, 이 수열의 합을 각각 $S_1$, $S_2$, $S_3$ 이라고 하자. 만약 왼쪽을 먼저 자.. [BOJ] 1693 트리 색칠하기 문제 링크: https://www.acmicpc.net/problem/1693문제 요약$n$개의 정점으로 구성된 트리가 있다. 이 트리를 $1$에서 $n$번까지의 색깔로 칠하는데 $k$번 색깔로 칠하는 데는 $k$만큼의 비용이 든다. 인접한 정점을 같은 색으로 칠하지 않으려고 할 때 최소 비용을 구하는 문제이다.풀이 과정이 문제를 푸는 데 가장 핵심적인 아이디어는, 트리를 색칠하는 데 많아 봐야 $\lg n$개의 색깔만이 필요하다는 것이다. 맨 처음에는 직관적으로 이 성질을 생각했는데, 좀 더 생각해보고 증명을 해 볼 수 있었다. 증명은 아래에!만약 트리를 색칠하는 데 필요한 색깔이 생각보다 적다는 것을 알게 되면, 다음과 같은 동적계획법을 생각해 볼 수 있다. $DP[a][c]=$ $a$번째 정점을 색.. [BOJ] 7579 앱 나는 사용가능한 최대 cost를 정해두고 0/1 knapsack을 돌리는걸 파라메트릭 서치로 해서 AC를 받았는데 보니까 아무도 이렇게 풀지 않았다 ㅠㅠ 억울해서 소스를 올린다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include using namespace std; int n,m;int arr[105];int cost[105];int cache[105][10005]; int dp(int idx, int remain){ if(idx==(n+1)) return 0; int& ret=cache[idx][remain]; if(ret!=-1) return ret; int ma=dp(id.. [BOJ] 2629 양팔저울 DP 정의는 $DP(i,j)$=i 이하 번호의 추를 사용하여 왼쪽 저울 - 오른쪽 저울의 무게가 j가 되게 할 수 있는가그러면 $DP(i,j)=DP(i+1,j+weight[i]) || DP(i+1,j-weight[i]) || DP(i+1,j)$라는 점화식이 세워짐. 왼쪽에 올리거나, 오른쪽에 올리거나, 아예 올리지 않거나. 간단한 DP problem 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include using namespace std; int f(int x){ return x+60000;} int n,m;int weight[35];int cache[35][120000]; int dp(in.. [BOJ] 11052 붕어빵 판매하기 문제: https://www.acmicpc.net/problem/11052 너무 쉬워서 자세한 설명은 생략한다. 난이도는 그냥 1/5 123456789101112131415161718192021222324252627282930313233343536#include #include #include #define INF (987654321) using namespace std; int n;int cost[1005];int cache[1005][1005]; int dp(int b, int c){ if(b==0) return 0; if(c>n) return -INF; int &ret=cache[b][c]; if(ret!=-1) return ret; int ma=0; for(int i=c;i [BOJ] 1005 ACM Craft 문제: https://www.acmicpc.net/problem/1005 위상 정렬의 대표격인 건설 순서 문제이다. 그런데 사실 난이도가 아주 없는 문제는 아니어서 이게 왜 1005번에 있나 조금 의심이 들기는 하는 부분이다. 사실 습격자 초라기에 비할 바는 못되지만... 하여튼 내 풀이를 설명하자면, DFS를 이용해 그래프를 순회하면서 함수가 종료할 때마다 저장하면 위상 정렬의 역순이 된다는 점을 이용해서 DP를 돌리는 방법으로 문제를 풀었다. 이를 위해서 순방향 간선과 역방향 간선의 인접 리스트를 별도로 만들었고, 역방향 간선의 인접 리스트의 크기가 0인 것들을 모두 DFS 돌리고 reverse해서 위상 정렬을 찾은 다음 그걸 역방향 간선 인접 리스트를 통해 바텀업 DP로 돌려서 결과값을 찾아냈다. .. 이전 1 다음