본문 바로가기

백준/DP

 (63)
[ICPC] 백준 23342 - Histogram https://www.acmicpc.net/problem/23242 서론 대회 때 누적합을 쓰는 dp겠거니 싶어서 시도해봤는데 풀지 못하고 도망쳤었다. 이번에 다른 풀이를 참조했는데 아마 대회 중에는 떠올리지 못했을 것이다. 테이블 설계 이 문제를 dp로 푸는 테이블은 다음과 같다. dp(i, j) := i번째 인덱스에서 버킷이 j개 남았을 때 분산의 최솟값 탑 다운 dp로 풀 때는 0부터 시작하는 다른 함수와 달리 n부터 시작하면서 내려가는 방식이다. 분산 구하기 중고등학교 교과 과정을 무사히 이수 했다면 모집단에서 분산을 구하는 식은 다음과 같음을 잘 알고 있다. $\sum(X - m)^{2}$ 우리는 위 분산 계산을 고속으로 하기 위해 식을 일부 전개 후 누적합을 사용할 것이다. $\sum (X^{..
백준 14437 - 준오는 심술쟁이!! https://www.acmicpc.net/problem/14437 주어진 문자열은 사실상 장식이고 꽤 어려운 동적 계획법 문제이다. 이 포스트에서는 1차원 테이블과 슬라이딩 윈도우를 결합한 방법을 소개한다. 다음 테이블 2개를 정의한다. dp_old(i) := 이전 인덱스 문자까지 총 i만큼의 숫자를 소진해서 문자열을 바꾸는 경우의 수 dp(i) := 현재 인덱스 문자까지 총 i만큼의 숫자를 소진해서 문자열을 바꾸는 경우의 수 이미 바꾼 문자는 다시는 바꿀 수 없으므로 이전 1~25만큼 바꿨을 때 문자열이 변하는 경우를 테이블에 반영하면서 전진하면 된다. 이때 처음 dp_old(0)은 공집합 1로 규정한다. 그리고 우리는 dp를 계산해야 되는데 문제의 k가 최대 25라는 조건이 있으므로 $dp(i) =..
[KOI] 백준 21759 - 두 개의 팀 https://www.acmicpc.net/problem/21759 이 포스트에서는 문제 지문을 완벽히 이해했다고 가정하고 풀이를 설명한다. 꽤 까다로운 트리 DP이다. 기본적인 트리 DP만 해봤다면 상당히 애를 먹을 수도 있다. 우선 다음 3개의 테이블이 필요하다. dp1(i) := i가 팀장이 되어 팀을 구성했을 때 최대 점수 dp2(i) := i가 팀장일 때 i의 자식 노드들에 대해 dp1(i)에 속하지 않은 정점을 대상으로 팀을 구성했을 때 최대 점수 dp3(i) := i가 루트인 서브 트리가 가질 수 있는 최대 점수 각 테이블을 계산해보자. 1. dp1을 계산하는 것은 쉽다. dfs 재귀로 합 dp를 수행하면 된다. 이때 자식 노드의 dp1 값이 음수인 경우는 더하지 않는 게 최적이다. 2. 자..
[KOI] 백준 2507 - 공주 구하기 https://www.acmicpc.net/problem/2507 발상 단순히 가는 경우면 어렵지 않게 계산할 수 있겠는데 구출하고 돌아와야 한다. 다음과 같은 생각을 해볼 수 있다. 갔다가 돌아오는 게 아니라 그냥 2명의 사람이 밟는 발판을 겹치지 않게 이동하기 이렇게 두면 테이블이 dp[501][501]인 dp 테이블을 구상할 수 있다. 위처럼 테이블을 두면 다음과 같은 점화식을 생각해볼 수 있다. f(i, j) := 공주를 구하기 위해 i번째 돌을 밟았고 도망치기 위해 j번째 돌을 밟는 경우의 수(거꾸로) 각각 i와 j에 대해 갈 수 있는 발판을 탐색하면서 경우의 수를 더하는 탑 다운 dp를 고려할 수 있다. 유의 사항 다만 이렇게 동적 계획법을 수행하면 주의해야 할 사항이 있다. 1. j는 목적지..
백준 1126 - 같은 탑 https://www.acmicpc.net/problem/1126 다음 점화식을 정의한다. dp(i, j) := i번째 블록에서 두 탑의 높이차가 j일 때 두 탑 중 높은 탑의 높이 그러면 다음과 같은 경우로 동적 계획법 계산을 할 수 있다. 1. i번째 블록을 쓰지 않는 경우 dp(i, j) = dp(i - 1, j) 2. i번째 블록을 높은 타워에 쌓는 경우 블록의 길이를 b라 하면 dp(i, j + b) = dp(i - 1, j) + b 3-1. i번째 블록을 낮은 타워에 쌓는데 그럼에도 불구하고 높은 타워보다 작은 경우 블록의 길이를 b라 하면 새로운 높이차 diff = j - b이다. 그러므로 dp(i, diff) = dp(i - 1, j) 3-2. i번째 블록을 낮은 타워에 쌓는데 높은 타워보..

티스토리툴바