[백준] 원자의 에너지

 

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

2058번: 원자의 에너지

 

문제 해석이 어려웠던 문제입니다. 질문 게시판의 지문 해석 글을 보지 않았다면 풀기가 힘들었을 문제입니다. 문제 이해 자체가 어려웠다면 해당 글을 참고해보시면 좋을 것 같습니다. 

 

결국, 원소의 상태간의 경로가 유일하게 존재한다는 의미는 원소의 상태를 그래프로 그리면 트리가 된다는 것을 의미합니다. 트리를 구축하기 위해서는 양성자를 더하거나 뺐을 때 원소의 상태로 존재할 수 있으면 간선이 있다는 것을 의미하게 됩니다. 이렇게 구축된 트리를 바탕으로 tree dp를 수행해주면 됩니다.

 

import sys
from collections import defaultdict

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

graph = defaultdict(list)
state = set()

proton = []

n, m = tuple(map(int, input().split()))

start_node = sys.maxsize

for _ in range(n):
    st = int(input())
    state.add(st)
    start_node = min(st, start_node)

# 원자의 상태를 정렬된 상태로 저장한다.
atomic = list(state)
atomic.sort()

idx_dict = defaultdict(int)

# 각 원소의 인덱스를 저장해놓는다.
for i, at in enumerate(atomic):
    idx_dict[at] = i

for _ in range(m):
    p = int(input())

    for st in state:
        if st - p in state:
            graph[idx_dict[st]].append(idx_dict[st - p])

        if st + p in state:
            graph[idx_dict[st]].append(idx_dict[st + p])


# dp[i][0]: i번째 원소를 추가한 경우
# dp[i][1] : i번째 원소를 추가하지 않은 경우
dp = [
    [0] * 2
    for _ in range(n + 1)
]

visited = set([0])

for i in range(0, n):
    dp[i][1] = atomic[i]

def dfs(cur):
    for next_node in graph[cur]:
        # 이미 방문한 지점이다.
        if next_node in visited:
            continue

        visited.add(next_node)

        dfs(next_node)

        # 현재 원자를 포함하지 않은 경우
        dp[cur][0] += max(dp[next_node][0], dp[next_node][1])
        dp[cur][1] += dp[next_node][0]


# 가장 에너지상태가 낮은 상태에서 시작해야한다.
dfs(0)

print(max(dp[0][0], dp[0][1]))