다이나믹프로그래밍 썸네일형 리스트형 BOJ 6171 땅따먹기 (볼록껍질 최적화) https://www.acmicpc.net/problem/6171 6171번: 땅따먹기 (1) / (4) / (2, 3) 으로 땅을 묶어 사보자. 상헌이는 100 * 1 + 20 * 15 + 1 * 100 = 500의 가격에 땅을 살 수 있다. www.acmicpc.net 볼록껍질 최적화가 일감 이었으나 쉽게 점화식을 유도하지는 못했다. 우선 두 개의 땅 a, b에 대해서 W_a >= W_b 이고 H_a >= H_b 이면, 땅 b는 땅 a와 한 묶음으로 사는게 무조건 이득이다(추가 비용이 발생하지 않는다). 전처리를 해서 b와 같은 땅을 모두 걸러낸 뒤, 너비에 대해서 오름차순으로 정렬을 하면 높이는 내림차순으로 정렬이 된다. 너비에 대해 정렬이된 세 개의 땅 a, b, c를 생각해보자. 이때 (a, c.. 더보기 BOJ 12766 지사 배정 (분할정복 동적계획법 최적화) https://www.acmicpc.net/problem/12766 12766번: 지사 배정 입력의 첫줄은 4개의 정수 n, b, s, 그리고 r로 이루어진다. n (2 ≤ n ≤ 5 000)은 교차로의 개수, b (1 ≤ b ≤ n − 1)는 지사의 수, s (1 ≤ s ≤ b)는 하위 프로젝트의 수, r (1 ≤ r ≤ 50 000)은 도로의 수를 www.acmicpc.net 방향그래프의 정점에 위치한 그래프들을 S개의 그룹으로 묶어, 한 그룹내에서 모든 지사들 사이에서 통신을 할 때, 총 통신비용을 최적화 하는 문제이다. 두 지사 사이의 통신은 항상 본부를 거쳐서 지나가야 한다. 따라서 본부 s에서 지사 u까지의 거리 D[s][u], 그리고 지사 u에서 본부 s까지의 거리를 D[u][s] 라고 하면.. 더보기 BOJ 5466 상인 (IOI 2009 Salesman) https://www.acmicpc.net/problem/5466 5466번: 상인 어떤 상인이 육지에서 최적 여행 스케줄을 구하는 것이 매우 어려웠기 때문에, 직선으로 흐르는 다뉴브강을 따라 이동하면서 물건을 팔기로 했다. 이 상인은 다뉴브 강을 따라 임의의 위치로부 www.acmicpc.net 문제 분석 단계에서 아래의 성질을 이용할 수 있지 않을까를 고민하다 결국 더 오래 걸린 문제 상인은 결국 시작점으로 돌아와야 한다. 따라서 올라간 거리의 합 = 내려간 거리의 합. DP 식을 잘 조작을 해서 컨벡스 홀 최적화나, 크누스 최적화를 적용하기. 위의 조건을 잊어버리고 그냥 각 경우 별 DP 점화식을 생각해 보면, 우선 시장들을 시장이 열리는 날짜 순으로 정렬을 한 뒤, DP[i] = i 번째 시장을 .. 더보기 BOJ 13972 파일합치기2 (크누스 최적화) https://www.acmicpc.net/problem/13974 13974번: 파일 합치기 2 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net dp[i][j] = i번 파일부터 j번 파일까지 합치는데 필요한 최소 비용이라고 정의하고, s[i][j] = i번 파일부터 j번 파일까지 파일 크기의 합이라 하면, 아래의 dp 점화식을 얻을 수 있다. dp[i][j] = min(i 더보기 이전 1 다음