[BOJ 16297] Eating Everything Efficiently

문제

---

https://www.acmicpc.net/problem/16297

풀이

---

조금 이색적인 문제였다.

DAG에서 순회하면서 노드 가중치 합의 최대를 구하는데, 꼭 더해야 하는 것은 아니며 대신 더할 때마다 1 / 2 ** k의 가중치가 추가로 곱해진다.

지금까지 선택한 노드의 개수와 현재 위치가 주어지면 부분 문제가 결정되므로 N * N DP 테이블을 만들어 풀려고 했으나 n이 최대 5 * 10 ** 5라서 바로 MLE가 나온다.

무한등비급수에서 아이디어를 얻어보면, 현재 위치만 주어져도 문제를 해결할 수 있다.

# i번째 노드를 선택할 때
res = max(res, enjoy[i] / 2 ** k + f(j, k + 1))

# i번째 노드를 건너뛸 때
res = max(res, f(j, k))

이런 식으로 현재 노드에 1 / 2 ** k 가중치를 곱해주는 게 아닌,

# i번째 노드를 선택할 때
res = max(res, enjoy[i] + f(j) / 2)

# i번째 노드를 건너뛸 때
res = max(res, f(j))

앞으로 얻을 합을 2로만 나눠주면 된다.

> 코드

---

import sys
sys.setrecursionlimit(5 * 10 ** 5)

n, m = map(int, sys.stdin.readline().split())
enjoy = list(map(int, sys.stdin.readline().split()))
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)

dp = [-1] * n


def f(i):
    if dp[i] != -1:
        return dp[i]
    
    res = enjoy[i]
    for j in graph[i]:
        res = max(res, enjoy[i] + f(j) / 2)
        res = max(res, f(j))
    
    dp[i] = res
    return res


print(f(0))