Atcoder에서 열렸던 Educational DP contest 문제들에 대한 풀이입니다. 자주 나오는 다이나믹 프로그래밍 유형들을 연습할 수 있는 좋은 셋이라고 생각합니다.

문제마다 간략한 풀이를 작성했습니다. 코드는 Atcoder에서 자유롭게 열람이 가능하므로 문제마다 링크를 달아두었습니다. 어느정도는 난이도 순서대로 정렬되어 있지만, 사람마다 느끼는 난이도가 다를 수 있습니다.

A. Frog 1

문제 링크

번째 Stone까지 도달하는 최소 비용

위와 같은 점화식으로 간단히 해결할 수 있는 쉬운 문제입니다.

코드(링크)

B. Frog 2

문제 링크

위 Frog 1 문제와 거의 비슷하게,

번째 Stone까지 도달하는 최소 비용

와 같이 쉽게 해결할 수 있습니다.

코드(링크)

C. Vacation

문제 링크

번째 날에 A행동을 했을 때, 번째 날까지 얻을 수 있는 최대 happiness

번째 날에 B행동을 했을 때, 번째 날까지 얻을 수 있는 최대 happiness

번째 날에 C행동을 했을 때, 번째 날까지 얻을 수 있는 최대 happiness

위와 같이 DP 식을 정의하면, 점화식은 다음과 같이 간단히 유도됩니다.

위 점화식을 가 커지는 순서에 따라서 채워주면 답은 으로 구할 수 있습니다.

코드(링크)

D. Knapsack 1

문제 링크

유명한 냅색 문제입니다.

번째 item까지 고려했을 때, 의 무게만큼 사용했을 때 얻을 수 있는 최대 value.

라고 정의합시다. 그러면 번째 item을 넣느냐 마느냐에 따라서 다음과 같은 점화식을 얻을 수 있습니다.

따라서 2차원 배열을 위 점화식에 따라 채우기만 하면 되므로 시간복잡도에 해결할 수 있습니다.

코드(링크)

E. Knapsack 2

문제 링크

위 Knapsack 1 문제와 비슷하지만, 이번에는 무게 의 범위가 크고, value 의 범위가 작다는 것에 착안해야 합니다. DP 정의를 조금 바꿔서

번째 item까지 고려했을 때, 의 value만큼 얻었을 때 가능한 최소 무게.

라고 정의합시다. 그러면 점화식은 위와 비슷하게 번째 item을 넣느냐 마느냐에 따라서 다음과 같이 작성할 수 있습니다.

이제 위 점화식에 따라서 2차원 DP 배열을 모두 계산한 뒤, DP값이 보다 작은 원소들 중 최대의 를 고르는 것이 답이 됩니다.

Knapsack 1/2 문제처럼 인자의 범위에 따라서 DP 정의를 유동적으로 바꿔야 하는 경우가 많습니다.

코드(링크)

F. LCS

문제 링크

유명한 LCS 문제입니다.

번째 문자, 번째 문자까지 고려했을 때 최대 LCS 길이.

로 정의하면, 가 같은지 다른지에 따라서 다음과 같은 점화식을 생각할 수 있습니다.

이러한 2차원 DP배열을 채우고 나면, 최종적인 LCS길이는 가 될 것입니다. 문제를 해결하려면 답을 역추적해야 되는데, 이는 해당 DP값이 , , 의 세 경우 중 어느 곳에서 왔는지 역으로 따라가면 됩니다. 의 transition이 발생할 때마다 해당 문자가 선택되었다는 뜻이므로 답에 추가해주면 됩니다.

코드(링크)

G. Longest

문제 링크

번 노드에서 시작하는 최장 경로 길이.

와 같이 정의한 뒤, Memoization을 이용해 Top Down 방식으로 각 DP값을 계산해 주면 됩니다. Cycle이 존재하지 않음이 보장되어 있으므로 시간복잡도에 해결이 가능합니다.

코드(링크)

H. Grid 1

문제 링크

위치에 도달할 수 있는 경우의 수.

와 같이 정의하면 DP 점화식은 다음과 같이 자연스럽게 유도됩니다.

(두 위치 중 벽이 아닌 곳들만 더해주어야 합니다)

이제 이 점화식을 통해 DP table을 시간에 계산하면 문제를 해결할 수 있습니다.

코드(링크)

I. Coins

문제 링크

번째 동전까지 고려했을 때, head가 개 나올 확률

와 같이 정의합시다. 그러면 각 동전마다 head가 나올 확률이 이므로 다음과 같은 점화식이 성립합니다.

이 점화식을 이용해 DP table의 값을 모두 계산한 뒤, 들 중 인 값들을 모두 더해주면 곧 답으로 원하는 확률이 나옵니다.

코드(링크)

J. Sushi

문제 링크

초밥이 개 남은 접시가 각각 개 남아있을 때, 다 먹을때까지 필요한 operation 횟수의 기댓값

와 같이 정의합시다. DP transition은 주사위를 굴렸을 때 나올 수 있는 경우에 따라서 경우를 나눌 수 있습니다. 먼저, 초밥이 하나도 없는 접시의 번호가 나오는 경우를 생각해 봅시다. 이 경우에는 의 계산에서 를 참조하기 때문에 cycle이 생기게 됩니다. 따라서 초밥이 적어도 하나 있는 접시의 번호가 나올 때까지 주사위를 굴리는 기댓값을 따로 구해주어야 합니다. 이는 Geometric Distribution이라는 것을 알 수 있는데, 원하는 기댓값은 곧 이라는 것이 잘 알려져 있습니다. 따라서 이 값을 먼저 더해준 뒤, 초밥이 개 남은 접시가 나오는 경우를 처리해주면 됩니다. 결론적으로 다음과 같은 DP 점화식을 얻을 수 있습니다.

이 점화식에 따라 DP table을 계산해준 뒤 답을 구할 수 있습니다.

코드(링크)

K. Stones

문제 링크

기초적인 게임이론 문제입니다.

개의 돌로 게임을 시작하면 선공이 이기는가?

와 같이 정의합시다. 만약 가 false인 가 존재한다면 는 true가 되고, 이러한 가 존재하지 않는다면 는 false가 됩니다.

따라서 시간복잡도로 모든 값을 계산해 주면 의 값에 따라 답을 결정할 수 있습니다.

코드(링크)

L. Deque

문제 링크

Taro의 전략은 를 최대화하는 것이고, Jiro의 전략은 를 최대화하는 것입니다. 따라서 둘 모두 (내 점수)-(상대방 점수) 를 최대화하고 싶어하는 것을 알 수 있습니다. 이를 통해 다음과 같은 DP 정의를 생각해 봅시다.

구간의 수가 남아있을 때, (내 점수)-(상대 점수)의 최댓값.

위와 같이 정의한 뒤 DP transition을 어떻게 할 수 있을지 생각해 봅시다. 내가 을 골랐다면 최종적으로 (내 점수)-(상대 점수)는 이 되고, 을 골랐다면 이 됩니다. 따라서 이 두 값 중 큰 값을 고르는 방식으로 점화식을 정의할 수 있습니다.

위 transition으로 DP table을 모두 채우면 이 최종적인 답이 됩니다.

코드(링크)

M. Candies

문제 링크

번째 아이들에게 총 개의 사탕을 나누어주는 방법의 수.

로 정의합시다. 그러면 번째 아이에게 사탕을 몇 개 나누어주었느냐에 따라 다음과 같은 점화식이 성립합니다.

그런데 이를 naive 하게 계산하면 시간복잡도 으로 충분히 빠르지 못합니다. 여기서 유명한 구간합 테크닉을 사용하면 되는데,

와 같이 구간합 배열을 정의한 뒤, 이를 사용해서 와 같이 빠르게 계산할 수 있습니다. 따라서 시간복잡도는 가 됩니다. 최종적인 답은 가 될 것입니다.

코드(링크)

N. Slimes

문제 링크

파일 합치기 와 완전히 동일한 문제입니다.

번째 파일을 하나로 합치는 최소 비용.

으로 정의합시다. 번째 파일이 하나로 합쳐지는 과정의 마지막 순간을 생각해 봅시다. 어떤 가 존재해서, 번째 파일들과, 번째 파일들이 각각 하나의 파일이 되어있는 상태에서 두 파일이 최종적으로 합쳐질 것입니다. 따라서 모든 가능한 에 대해 시도해보는 것으로 최소 비용을 계산할 수 있습니다.

위와 같은 점화식을 순서에 맞게 잘 채워주면 최종 답은 이 됩니다.

코드(링크)

O. Matching

문제 링크

명의 여성들 중, 매칭된 여성들을 비트마스크로 나타낸 집합을 으로 표현합니다. 다음과 같은 DP 정의를 생각합니다.

번 남성까지 매칭시켰을 때, 매칭된 여성들의 집합이 인 경우의 수.

그러면 번 남성이 어떤 여성과 매칭되느냐에 따라 다음과 같은 DP 점화식을 세울 수 있습니다.

위 식을 이 커지는 순서로 잘 계산해 주면 문제를 해결할 수 있습니다. 시간복잡도로는 약간의 컷팅이 더 필요할 수 있습니다. 코드를 보시면 한가지 방법이 나와 있습니다.

코드(링크)

P. Independent Set

문제 링크

가장 기본적인 Tree DP 문제입니다.

x를 반드시 색칠할 때, x를 루트로 하는 서브트리를 색칠하는 방법의 수.

x를 반드시 색칠하지 않을 때, x를 루트로 하는 서브트리를 색칠하는 방법의 수.

와 같이 두가지 경우로 나눠서 생각합시다.

가 색칠되면, 바로 밑의 자식들은 반드시 색칠되지 않아야 할 것입니다. 가 색칠되지 않으면, 바로 밑의 자식들은 색칠되거나, 안되거나 두 경우 모두 가능할 것입니다. 따라서 다음과 같은 점화식이 쉽게 유도됩니다. 는 노드 의 자식들의 집합입니다.

이제 위 값들을 DFS finish time 기준으로 채워 주면 됩니다. 편의상 1번 노드를 루트라고 하면 최종 답은 이 될 것입니다.

코드(링크)

Q. Flowers

문제 링크

이 주어졌을 때, 증가 부분 수열 중 그 합이 최대가 되도록 고르는 문제입니다.

다음과 같은 DP 정의를 생각해 봅시다.

에서 끝나는 증가 부분 수열 중 최대 합.

그러면 자연스럽게 아래처럼 점화식을 유도할 수 있습니다.

그런데 이를 가 증가하는 순서대로 naive하게 계산하면 시간복잡도로 충분히 빠르지 못합니다.

들을 오름차순으로 정렬한 뒤, 증가하는 순서대로 본다고 생각해 봅시다. 가 증가하는 순서대로 보고 있기 때문에, 를 계산하려면 이미 등장한 수들 중 보다 왼쪽에 있는 수들만 고려하면 될 것입니다. 또한, DP 점화식을 살펴보면 간단한 range max 쿼리 형태라는 것을 알 수 있습니다. 따라서 세그먼트 트리를 이용해 효율적으로 DP 값을 계산할 수 있습니다.

가 커지는 순서대로 를 계산할 때 세그먼트 트리의 range max 쿼리를 이용하고, 가 계산될 때마다 세그먼트 트리에 값을 update 해주는 방식으로 시간복잡도에 모든 DP 값을 계산할 수 있습니다. 최종적인 답은 이 될 것입니다.

코드(링크)

R. Walk

문제 링크

번 노드에서 끝나는 길이 짜리 경로의 가짓수.

처럼 정의합시다. 다음과 같이 DP transition을 생각할 수 있습니다.

이 식의 형태를 생각해 봅시다. 길이가 에서 끝나는 경로의 가짓수는 결국 길이가 인 경로들 중, 마지막 노드에서 로 향하는 edge가 존재하는 것들의 합이 된다는 것입니다. 이를 이용해 다음과 같이 행렬을 이용한 형태로 식을 표현할 수 있습니다.

따라서 각 는 다음과 같이 계산할 수 있습니다.

이제 거듭제곱을 시간복잡도에 수행하는 알고리즘을 이용해 adjacency matrix의 승을 계산해주기만 하면 답을 구할 수 있습니다. 최종적인 시간복잡도는 가 될 것입니다.

코드(링크)

S. Digit Sum

문제 링크

큰 자릿수부터 순서대로 채워 내려간다고 생각해 봅시다.

번째 자릿수까지 와 일치했고, 자릿수 합을 로 나눈 나머지는

번째 자릿수 또는 그 이전에서 보다 작아졌고, 자릿수 합을 로 나눈 나머지는

이제 번째 자릿수에 어떤 수를 채워넣느냐에 따라 DP transition을 생각할 수 있습니다.

의 경우 반드시 번째 자리에 를 넣어야 할 것이고, 의 경우에는 를 자유롭게 넣을 수 있습니다. 다만 여기서, 번째 자리에서 처음으로 보다 작아지는 경우만 잘 고려하면 됩니다. 따라서 다음과 같은 DP transition으로 계산할 수 있습니다.

를 계산할 때, 두번째 항이 바로 번째 위치에서 처음으로 보다 작아지는 경우를 처리하는 것입니다. 뺄셈 연산을 할 때 음수가 되는 경우를 주의합시다.

위 식에 따라서 DP값을 모두 계산해 주면 이 최종적인 답이 됩니다. 1을 빼주는 이유는 0을 답에서 제외해야 하기 때문입니다.

코드(링크)

T. Permutation

문제 링크

Permutation의 앞 수부터 하나씩 정해간다고 생각해 봅시다. 다만, 의 수를 사용해서 만든다고 생각합시다.

번째 수까지 를 이용해 정했고, 마지막 수 인 방법의 수.

이제 DP transition을 생각하기 위해 를 어떻게 채울 것인가 생각해 봅시다. 을 이용해 만드는 상황입니다. 마지막 수가 라는 것은, 를 제외한 나머지 개의 수 을 구성하고 있다는 의미입니다. 이제 이러한 개의 수들을 상대적인 크기에 따라 다시 으로 압축해서 생각할 수 있습니다. 다시 말해, 첫 개의 수를 으로 고정시키고, 추가되는 번째 수를 처럼 생각한다는 것입니다. 그러면 다음과 같은 DP transition이 가능합니다.

위 식을 그대로 계산하면 이지만, 구간합 배열을 간단히 응용해 에 모든 DP값을 계산할 수 있습니다. 최종적인 답은 가 될 것입니다.

코드(링크)

U. Grouping

문제 링크

토끼들의 집합 을 비트마스크로 나타낸 것을 소문자 으로 표현합시다.

먼저 다음과 같은 배열을 시간에 계산해 둡시다.

집합 에 해당하는 토끼들이 한 그룹으로 묶였을 때, 그 그룹으로 얻는 점수

이제 다음과 같은 DP 식을 생각합시다.

집합 에 해당하는 토끼들을 잘 나누어서, 최대로 얻을 수 있는 점수

집합 의 임의의 부분집합 를 모두 시도해보는 것으로 다음과 같은 점화식을 생각할 수 있습니다.

이를 순서를 잘 정해서 채워주기만 하면 최종적인 답은 가 됩니다.

집합 으로 개가 가능하고, 각 을 채울 때 최대 개의 부분집합을 시도해야 해서 총 시간복잡도가 이 된다고 생각할 수 있으나, 실제로는 부분집합의 개수가 그렇게 많지 않기 때문에 훨씬 빠르게 작동하는 것을 알 수 있습니다.

코드(링크)

V. Subtree

문제 링크

문제의 조건은 결국 색칠된 정점들이 하나의 연결된 component를 이루어야 한다는 것입니다. 다음과 같은 두 DP 정의를 생각합시다.

정점 를 반드시 색칠하고, 를 루트로 하는 서브트리를 색칠하는 방법의 수.

정점 를 반드시 색칠하고, 의 위쪽 서브트리를 색칠하는 방법의 수.

여기서 의 위쪽 서브트리란, 전체 트리에서 를 루트로 하는 서브트리를 제외한 트리를 말합니다.

위 두 값을 모두 계산해두면, 를 반드시 색칠하는 경우의 답은 가 됩니다.

두 식은 각각 다음과 같이 계산할 수 있습니다. 여기서 의 자식 정점들의 집합이고, 의 부모 정점입니다.

위 식을 일반적인 tree dp 를 하듯이 계산해 주면 됩니다. 는 간단한 DFS로 쉽게 계산할 수 있고, 는 구간 곱 배열을 응용하면 총 시간에 모든 값을 계산할 수 있습니다. 자세한 구현방법은 코드를 보는 것이 도움이 될 것입니다. 저는 DFS를 돌면서 현재 정점의 자식들의 값을 계산해주는 방식으로 구현했습니다.

코드(링크)

W. Intervals

문제 링크

string의 번째 글자까지 결정했고, 마지막 번째 글자가 1인 경우의 최대 score.

위와 같은 DP 정의를 생각합시다. 번째 글자 직전에 나오는 1의 위치를 라고 생각하면 다음과 같은 점화식을 생각할 수 있습니다. 번째 위치의 1에 의해 score에 반영해야 하는 구간들의 점수를 더해주는 것입니다.

위 식을 그대로 계산하면 시간복잡도가 되어 충분히 빠르지 못합니다.

값이 뒤의 값에 어떻게 영향을 주는 지 생각해 봅시다. 보다 이후에 열리고, 보다 이후에 닫히는 구간들의 값이 에 더해져서 에 반영이 되는 형태입니다. 따라서 모든 구간들을 open, close 위치 기준으로 정리해 놓읍시다. index 를 하나하나 증가시켜 가면서, 위치에서 열리는 구간들의 값을 구간의 값들에 더해 줍시다. 또한 위치에서 닫히는 구간들의 값도 구간의 값들에 빼 줍니다. 이후 를 결정하려면 위 값들이 반영된 중 최댓값이 가 될 것입니다. Range add / Range max query 를 처리하기 위해 segment tree + lazy propagation을 사용하면 시간복잡도에 문제를 해결할 수 있습니다.

코드(링크)

X. Tower

문제 링크

먼저, 블록들을 어떤 순서로 쌓아야 최적일지 생각해 봅시다. 속성을 가지는 1번 블록과, 속성을 가지는 2번 블록의 순서를 결정한다고 생각합시다. 1번 블록이 2번 아래에 오는 경우에는 위로 더 쌓을 수 있는 무게가 입니다. 반대로 2번 블록이 1번 아래에 오는 경우에는 위로 더 쌓을 수 있는 무게가 입니다. 1번 블록이 아래에 오는 것이 유리하려면 부등식을 만족해야 된다는 것을 알 수 있습니다. 이를 다시 적어보면, 가 되는데, 즉 가 작은 블록일수록 아래에 오는 것이 유리하다는 뜻이 됩니다. (이러한 테크닉을 Exchange Arguments Technique 이라고도 합니다.)

위 결과에 따라 모든 블럭을 의 오름차순으로 정렬하고 시작합시다. 정렬된 순서대로 선택한다는 것을 알고 있으니, 어떤 블록들을 선택할지만 문제가 됩니다. 이제 다음과 같은 DP 정의를 생각합시다.

번째 블록까지 고려했고, 위로 만큼의 무게를 더 견딜 수 있을 때 최대 value.

이제 번째 블록을 선택하는지 여부에 따라 다음과 같은 transition 이 정의됩니다. 이 때 기준으로 다음 state에 뿌려주는 방식으로 구현하는 것이 편합니다. 다음과 같은 형태로 구현이 될 것입니다.

의 최대 범위는 이므로 무난히 시간복잡도로 통과 가능합니다. 최종적인 답은 가능한 들에 대해 들 중 최댓값이 될 것입니다.

코드(링크)

Y. Grid 2

문제 링크

H. Grid 1 문제의 고난이도 버전입니다. 가 커져서 시간복잡도로는 문제를 해결할 수 없습니다.

모든 벽을 의 오름차순으로 정렬하고 시작합시다. 그리고 다음과 같이 DP 정의를 생각합시다.

빈칸만 거쳐서 번째 벽에 도달하는 방법의 수. 다시 말해, 번째 벽에 도달하는데 그것이 처음으로 만나는 벽인 경로의 수.

벽들을 좌표 순서대로 정렬한 이유는 번째 벽에 도달하기 전에 거쳐올 수 있는 벽들은 반드시 보다 index가 작아지도록 하기 위함이었습니다.

처음으로 만나는 벽이라는 조건 없이 에 도달하는 경우의 수는 입니다. 여기서 이전에 이미 벽을 만난 경우를 빼 주면 을 계산할 수 있습니다.

번째 벽 직전에 만난 벽은 어떤 것들일지 생각해 봅시다. 위에서 벽들을 좌표 순서대로 정렬했기 때문에 index 는 반드시 보다 작아야 할 것입니다. 또한, 을 모두 만족해야 할 것입니다. 이 조건들을 만족하는 모든 들에 대해,
에서 빼 주면 됩니다.

DP transition은 이미 충분히 설명했으므로 식을 따로 적진 않겠습니다. 위와 같은 방법으로 을 계산하면, 정의대로 모든 경로를 잘 고려한다는 것을 이해하는 것이 중요합니다.

번째 점이 있다고 가정하고 문제를 풀면 이 답이 됩니다.

코드(링크)

Z. Frog 3

문제 링크

아주 유명한 Convex hull trick 문제입니다. Convex hull trick문제와 해결방법에 대해서는 다른 글(링크) 을 참고하시기 바랍니다.

먼저 다음과 같은 간단한 DP 정의를 생각합니다.

번 stone에 도달하는 최소 비용.

DP transition은 다음과 같이 정의됩니다.

이 식을 조금 변형해 봅시다.

기울기가 이고, 절편이 인 직선이 추가되는 Convex hull trick 문제의 형태로 변형되었습니다.

이제 Convex hull trick을 푸는 다양한 방법들 중 아무 것이나 적용해서 문제를 해결하면 됩니다. 이 문제의 경우는 가 커질수록 추가되는 직선의 기울기가 작아진다는 성질을 이용하면 Lichao Tree 등의 자료구조를 굳이 사용하지 않아도 해결할 수 있습니다.

코드(링크)