AtCoder Educational DP Contest

Round 링크: Top / Tasks
소멤 블로그 풀이: 링크

아주 교육적인 DP 문제 모음집이다. 여기서는 간략하게 풀이를 정리해본다.

A, B - Frog 1, 2

문제 링크(A): https://atcoder.jp/contests/dp/tasks/dp_a
문제 링크(B): https://atcoder.jp/contests/dp/tasks/dp_b
문제 예상 티어: Min - Silver III / Max - Silver I

$DP[i]$ 가 최소 비용을 들고 있게끔 하면 되는 유형. 계단 오르는 문제랑도 비슷하다. B번의 경우에는 최대 $K \le 100$ 까지 이동 가능하다는 조건이 있다. B번에서 달라지는 것은 $i$ 가 증가할 때마다 최대 $K$ 이전 index까지 확인해서 들고오면 된다는 점.

C - Vacation

문제 링크: https://atcoder.jp/contests/dp/tasks/dp_c
문제 예상 티어: Silver I

이번에는 마지막 상태를 같이 저장하고 있을 필요가 있다. 왜냐면, 같은 활동을 2일 연속 하지 못하기 때문에, $i$ 번째 날의 활동을 하면서 얻은 max 행복도와 더불어, 그것을 달성했을 때 어떤 활동을 했었는지가 저장이 되어야 하는 것. 이런 유형에서는 보통 DP의 차원을 늘려서 해결하곤 한다. $DP[k][i]$ 를 선언하여, 각 값이 i번째날에서의 max 행복도를 저장하되 그 마지막 활동이 k인 경우라고 생각하면 된다.

D, E - Knapsack 1, 2

문제 링크(D): https://atcoder.jp/contests/dp/tasks/dp_d
문제 링크(E): https://atcoder.jp/contests/dp/tasks/dp_e
문제 예상 티어: Min - Gold V / Max - Gold III

이름부터 대놓고 유형을 암시한다. 일반적으로 Knapsack 유형은 무게의 상한이 $W \le 10^6$ 정도로 주고 그 무게 기준으로 생각할 수 있게끔 해서 풀리는데, D번은 완전 그 유형이고, E번은 한번 꼬았다.

E번의 경우에는 $W \le 10^9$ 이기 때문에, 오히려 $V \le 10^3$ 은 점을 이용하면 된다. 문제에서 $N \le 100$ 이기 때문에, 최대 행복도의 제한은 $V \le 10^5$ 가 되고, 해당 $V$ 에서의 최소 $W$ 를 저장해둔 후, 나중에 max $V$ 를 보면서 $W$ 가 유효한지(최대 제한에 안터졌는지) 확인하면 된다. 아래 BOJ 문제에서 많이 당했었다.

BOJ 7579번 “앱” 문제: https://www.acmicpc.net/problem/7579

F - LCS

문제 링크: https://atcoder.jp/contests/dp/tasks/dp_f
문제 예상 티어: Gold I

역시 대표 유형. 관련해서는 아래에 정리해두었다.

LCS: 링크

G - Longest Path

문제 링크: https://atcoder.jp/contests/dp/tasks/dp_g
문제 예상 티어: Gold II

Tree DP 유형하고 유사한 문제. 풀이는 여러 방법이 존재하는 것 같지만 일단 일반적인 Tree 처럼 풀 수는 없다. (방향이 있는 그래프)

indegree가 0인 정점들을 출발점으로 잡고 시작한 다음, leaf에 도달했을 경우부터 시작해서 depth를 채워주는 방식으로 하면, 중복방문을 피하면서 모든 정점의 depth를 채울 수 있다. 이들 중 max 값을 구하면 그래프에서의 가장 긴 경로의 거리가 된다.

풀이·코드 펼치기

struct Node {
    int depth;
    int inCnt;
    vector<int> edges;
} n[100010];

int dfs(int i) {
    if (n[i].edges.size() == 0) {
        // leaf
        return 0;
    }
    if (n[i].depth != 0) return n[i].depth;

    for(auto& t: n[i].edges) {
        int res = dfs(t);
        n[i].depth = max(n[i].depth, res + 1);
    }
    return n[i].depth;
}
void solve() {
    int ans = 0;
    for(int i = 1; i <= N; ++i) {
        if (n[i].inCnt == 0) {
            ans = max(ans, dfs(i));
        }
    }
    printf("%d", ans);
}

H - Grid 1

문제 링크: https://atcoder.jp/contests/dp/tasks/dp_h
문제 예상 티어: Gold V

빈출 유형. Grid에서의 이동 방향은 아랫 방향과 우측 뿐이기 때문에, 역으로 경우의 수는 위쪽과 왼쪽에서 오는 것의 합으로 구해주면 된다. 다만, 현재 위치가 벽일 경우 그 값을 0으로 초기화하는 것은 잊어서는 안된다.

I - Coins

문제 링크: https://atcoder.jp/contests/dp/tasks/dp_i
문제 예상 티어: Gold III

흔히 확률 DP라고 불리는 유형인 듯 하다. 단계별로 생각해보자.

앞면이 0개인 경우의 확률
- $(1 - p_1)(1 - p_2)(1 - p_3)...(1 - p_N)$
앞면이 1개인 경우의 확률
- $p_1(1 - p_2)(1 - p_3)...(1 - p_N) + (1 - p_1)p_2(1 - p_3)...(1 - p_N) + ... + (1 - p_1)(1 - p_2)(1 - p_3)...(1 - p_{N-1})p_N$
앞면이 N개인 경우의 확률
- $p_1p_2p_3...p_N$

그런데, 이것을 한번에 다 계산하기엔 연산량이 너무 많다. 이를 줄이기 위해 DP의 주요 풀이법 중 하나인 작은 경우부터 시작해보는 기법을 적용해볼 수 있다. $DP[i][j]$ 를 $i$ 번째 동전까지를 고려했을 때 $j$ 개가 앞면인 확률로 정의하자. 그러면 정의에 의해, $DP[1][0] = 1 - p_1$ , $DP[1][1] = p_1$ 이 된다. 이 상태로부터 시작하면, 상태 전이를 시킬 수 있다. $i$ 가 작은 경우부터 한번 따라가보자.

i = 2인 경우
- $DP[2][0] = DP[1][0] \times (1 - p_2)$
- $DP[2][1] = DP[1][0] \times p_2 + DP[1][1] \times (1 - p_2)$
- $DP[2][2] = DP[1][1] \times p_2$
i = 3인 경우
- $DP[3][0] = DP[2][0] \times (1 - p_3)$
- $DP[3][1] = DP[2][0] \times p_3 + DP[2][1] \times (1 - p_3)$
- $DP[3][2] = DP[2][1] \times p_3 + DP[2][2] \times (1 - p_3)$
- $DP[3][3] = DP[2][2] \times p_3$

여기까지 보면 규칙이 보인다. 전부 다 앞면인 경우와 전부 다 뒷면인 경우를 제외하면, 확률 상태전이가 $j$ 와 $j-1$ 두 곳에서 올 수 있다. 이를 통해 구현할 수 있다.

풀이·코드 펼치기

// 초기조건
DP[1][0] = 1.0 - p[1];
DP[1][1] = p[1];

for(int i = 2; i <= N; ++i) {
    for(int j = 0; j <= i; ++j) {
        if (j == 0) {
            DP[i][0] = DP[i - 1][0] * (1 - p[i]);
        } else if (j < i) {
            DP[i][j] = DP[i - 1][j] * (1 - p[i]) + DP[i - 1][j - 1] * p[i];
        } else {
            DP[i][j] = DP[i - 1][j - 1] * p[i]; 
        }
    }
}

최종적으로 구하고자 하는 것은 앞면이 뒷면보다 많이 나왔을 때인데, 이것은 $DP[N][N/2+1]$ ~ $DP[N][N]$ 의 합을 구하면 계산된다.

J - Sushi

문제 링크: https://atcoder.jp/contests/dp/tasks/dp_j
문제 예상 티어: Platinum V
nicotina04 님의 설명: https://nicotina04.tistory.com/275
기댓값 이론 정리: 링크

기댓값 DP. J번은 풀이에 실패했다. 핵심은 $DP[i][j][k]$ 를 특정 상태에서의 기댓값으로 정의하는데, $i$ , $j$ , $k$ 는 각각 초밥이 1개, 2개, 3개 남은 접시의 수로 정의해서 상태공간을 줄이는 것이 아이디어의 핵심이다.

I번에서는 $i$ 개의 동전을 고려한 상태에서 $i+1$ 개의 동전을 고려한 상황으로 전이를 했었다. 이와 유사하게 할 수 있다. $N=4, i=1, j=1, k=1$ 인 상황을 가정해보자.

해당하는 상황은 $DP[1][1][1]$ 로 볼 수 있다.
$p = \frac 1 4$ 로 이미 아무것도 없는 접시를 고른다. 상태가 자기 자신으로 전이된다.
$p = \frac 1 4$ 로 초밥이 1개 있는 접시를 고른다. 상태가 $DP[0][1][1]$ 로 전이된다.
$p = \frac 1 4$ 로 초밥이 2개 있는 접시를 고른다. 상태가 $DP[2][0][1]$ 로 전이된다.
$p = \frac 1 4$ 로 초밥이 3개 있는 접시를 고른다. 상태가 $DP[1][2][0]$ 로 전이된다.

그런데 위처럼 생각하다보니 문제가 하나 있다. 바로 1번 상황인데, 이 경우 자기 자신을 참조하는 상황이 된다. 그렇지만, 위 링크에 정리한 이론처럼, 전이되어 오는 확률들을 곱해서 계산하게 되므로 수식을 전개하는데에 문제는 없다. 위 4가지 case를 한번에 정리하면 아래와 같이 된다.

$DP[1][1][1] = \frac 1 4 (DP[1][1][1] + DP[0][1][1] + DP[2][0][1] + DP[1][2][0]) + 1$

이 수식을 전개해서 풀면 된다. 결국은 이 케이스를 확장해서 일반화한 수식으로 계산하면 문제가 풀린다.

$DP[i][j][k] = \frac {N - i - j - k} N DP[i][j][k] \newline \quad\quad\quad\quad\quad\quad + \frac i N DP[i - 1][j][k] \newline \quad\quad\quad\quad\quad\quad + \frac j N DP[i + 1][j - 1][k] \newline \quad\quad\quad\quad\quad\quad + \frac k N DP[i][j + 1][k - 1] \newline \quad\quad\quad\quad\quad\quad + 1$

K - Stones

문제 링크: https://atcoder.jp/contests/dp/tasks/dp_k
문제 예상 티어: Gold I
Editorial (일본어): https://qiita.com/drken/items/4e1bcf8413af16cb62da

풀이 실패 2. 상당히 알려진 문제 유형이지만, 이 문제를 접하기 전까지 게임이론 자체에 대해서 정리를 아예 하지 않았었다. 위 에디토리얼 글이 상당히 잘 되어 있어서, 해당 글을 바탕으로 정리를 좀 해보려고 한다.

문제를 단순화해서, K개의 돌무덤에서 2명의 플레이어가 1개, 2개, 3개 단위로만 돌을 빼낼 수 있다고 가정하고 문제를 생각해보자. (문제 조건과 동일하게 더 이상 돌무덤에서 돌을 가져가지 못하는 플레이어의 패배이다) 이 문제의 해법은 마치 베스킨라빈스 31 게임과 유사한데, 아래와 같음이 알려져 있다.

K가 4의 배수라면, 후수 필승
K가 4의 배수가 아니라면, 선수 필승

게임과정을 생각해보면, 각 상태에서 선공이든 후공이든 남은 돌의 수를 4의 배수로 맞추게 되면, 상대가 돌을 몇개를 가져가든 승리할 수 있음을 알 수 있다. 마지막 상황을 생각한 다음 사고를 확장하면 된다.

$K = 0$ , 현재 턴의 플레이어의 패배이다. (가져갈게 없음)
$K \le 3$ , 현재 턴의 플레이어의 승리! 다 가져가면 된다.
$K = 4$ , 현재 턴의 플레이어의 패배이다. 어떻게 가져가도 패배하게 된다.
$K = 5$ , 현재 턴의 플레이어의 승리! 4가 패배하는 flag이므로, 1개만 가져가면 된다.
$K = 6, 7$ , 현재 턴의 플레이어의 승리! 5일 때의 전략과 마찬가지로 하면 된다.
$K = 8$ , 현재 턴의 플레이어의 패배이다. $K = 4$ 와 유사하게, 어떻게 가져가더라도 $K = 4$ 로 전이되게 되어 패배하게 된다.

이 역시 일종의 DP로, $DP[0]$ 부터 시작해서 전이시키면서 구할 수 있다.

… How?