백준/DP (67) 썸네일형 리스트형 백준 2315 - 가로등 끄기 www.acmicpc.net/problem/2315 점화식 하는 방법을 익히면 어렵지 않게 풀 수 있다. 마징가가 가로등을 끄는 시간은 0이기 때문에 어떤 가로등을 끄지 않고 지나가면 최적해에 도달할 수 없음을 그리디 속성으로 이해할 수 있다. 따라서 마징가가 어떤 구간을 지나간다고 하면 구간에 속한 가로등은 모두 꺼진 상태여야 한다. 마징가가 어떤 구간에 속한 가로등을 모두 끄고 나면 구간의 끝에 위치하게 되므로 다음과 같은 점화식을 세울 수 있다. $f(l, r, direction) = $ l번부터 r번 가로등까지 끈 상태이고 마징가가 direction 방향 끝에 있을 때 소비된 전력양의 최솟값 전력 소비량 계산 누적합으로 구간 전력 소비량을 저장하면 특정 구간에서 소비되는 전력의 소비량을 $O(1).. [KOI] 백준 10835 - 카드게임 www.acmicpc.net/problem/10835 다음 가지치기로 얻을 수 있는 최대 점수를 동적계획법으로 구하면 된다. 왼쪽 카드를 버렸을 때 / 양쪽 카드를 버렸을 때 / 오른쪽 카드를 버릴 수 있을 경우 버리고 점수를 얻었을 때 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 #include using namespace std; int n; int l[2000], r[2000]; int dp[2000][2000]; int memo(int ldx, int rdx); int main() { memset(dp, -1, sizeof dp); .. 백준 1311 - 할 일 정하기 1 www.acmicpc.net/problem/1311 어렵지 않은 비트마스크 dp이다. 다음 dp테이블을 정의하고 탑 다운 dp로 풀면 된다. dp[i] = 비트마스크 i의 조합으로 일을 할당했을 때 비용의 최솟값 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 #include using namespace std; int n; int ar[20][20]; int dp[1 n; for (int i = 0; i ar[i][j]; memset(dp, -1, sizeof dp); int res = 1e9; for (.. [USACO] 백준 14165 - Team Building www.acmicpc.net/problem/14165 문제 소개 농부 존과 폴은 스테이트 페어에서 best in show라는 경쟁을 한다. 서로 가지고 있는 소들에게 점수를 부여하고 각 농부가 K마리의 소를 서로 점수가 높은 순으로 매칭하는데 한 진영의 소가 다른 진영의 소보다 모두 높은 점수로 매칭되면 이긴다. K가 주어지고 농부 존과 폴이 각각 N, M마리의 소를 가지고 있을 때 존이 이기는 경우의 수를 $10^9 + 9$로 나눈 모듈러를 출력해야 한다. 풀이 단순하게 존이 i번째 소, 폴이 j번째 소까지 각각 k마리를 뽑아서 존이 이기는 경우를 삼차원 동적계획법으로 풀 수 있다. (dp[i][j][k]) 다만 서로의 소를 매칭하는 경우를 일일이 탐색하면 시간복잡도는 $O(NM \times NMK)$.. [KOI] 백준 1866 - 택배 www.acmicpc.net/problem/1866 사전 지식 이 문제를 풀기 전에 USACO wifi setup과 BOJ 14400을 풀고 오는 것을 추천한다. 솔루션 - 편의점 2 / 솔루션 - wifi setup 풀이 트럭과 헬기를 적절히 써서 비용의 합을 최소로 해야한다. 비용의 최소는 wifi setup과 비슷하게 일차원 동적계획법으로 계산할 수 있다. 테이블의 정의는 dp[i] := i번째 지점까지 배송했을 때 비용의 최소 로 할 수 있으며 i번째 지점을 트럭으로 배송하거나 헬기로 어떤 지점에 물건을 나르고 그 지점에서 i번째 지점으로 트럭이 오는 경우로 나눠 계산하게 된다. 헬기로 배송한다고 했을 때 가장 이득을 보는 위치는 어떤 구간을 배송하기 위해 헬기를 이용할 때 그 구간의 중간 지점이.. 이전 1 ··· 3 4 5 6 7 8 9 ··· 14 다음
