[백준][Python] 2058 원자와 에너지

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

2058번: 원자의 에너지

 

tree_DP기본문제다.. 근데 안풀린다.. 다른문제로 연습하고 다시 도전할 것.

문제를 이해 못한건지 그냥 안풀린다.// 풀었음

정렬해서 한쪽 끝에서만 더하면 될 줄 알았는데 반례가 많은 것같다. 모든 시작지점에서 부터 돌렸다.

다시풀었는데 그냥 양성자를 빼는 경우만 고려해주면 시작점에서만 시작하면 되더라.

시간 500 -> 140 -> 120 까지 줄이고 종료.

 

+gap만 조사

import sys
input = sys.stdin.readline

# tree에 진입합니다.
def dfs(cur_atom):
    visited[cur_atom] = True
    dp[cur_atom][1] = cur_atom
    for gap in plus:                    # plus는 양성자크기들의 배열입니다.
        next_atom = cur_atom + gap      # 다음 노드는 지금 노드에서 양성자를 더해 갈수있는 위치입니다.
        if next_atom in visited:
            dfs(next_atom)
                                        # 상태인자 1은 현 노드를 가져가는 선택지, 0은 가져가지 않는 선택지입니다.
            dp[cur_atom][0] += max(dp[next_atom][1], dp[next_atom][0])      
            dp[cur_atom][1] += dp[next_atom][0]

# 각 atom_e상태가 plus를 받아들이거나 빼서 다른 atom_e에 도달할 수 있다.
# 그러나 인접한 에너지 준위가 존재하면 안된다.
# 어떤 atom_e의 조합을 선택해야 합이 최대가 되는가?
N, M = map(int, input().split())
atom_e = [int(input()) for _ in range(N)]
atom_e.sort()                                   # 낮은 에너지 준위부터 검사하기 위한 정렬
visited = {atom: False for atom in atom_e}      # 한번 방문한 노드를 방문하지 않기위한 check_list
dp = {atom: [0,0] for atom in atom_e}           # 각 선택지에 대해 최댓값을 저장할 dict
plus = [int(input()) for _ in range(M)]         # 각 에너지 준위 간의 차이값이 될 선택지인 양성자 크기 배열

max_sum = 0
for atom in atom_e:
    if not visited[atom]:                       # 모든 에너지준위에 대해 검사
        dfs(atom)
        max_sum += max(dp[atom][0], dp[atom][1])
print(max_sum)

 

-gap도 조사

 

import sys
input = sys.stdin.readline

# tree에 진입합니다.
def dfs(cur_atom):
    visited[cur_atom] = True
    dp[cur_atom][1] = cur_atom
    for gap in plus:                    # plus는 양성자크기들의 배열입니다.
        for next_atom in (cur_atom+gap,cur_atom-gap):    # 다음 노드는 지금 노드에서 양성자를 더해 갈수있는 위치입니다.
            if next_atom in visited and not visited[next_atom]:
                dfs(next_atom)
                                            # 상태인자 1은 현 노드를 가져가는 선택지, 0은 가져가지 않는 선택지입니다.
                dp[cur_atom][0] += max(dp[next_atom][1], dp[next_atom][0])      
                dp[cur_atom][1] += dp[next_atom][0]

# 각 atom_e상태가 plus를 받아들이거나 빼서 다른 atom_e에 도달할 수 있다.
# 그러나 인접한 에너지 준위가 존재하면 안된다.
# 어떤 atom_e의 조합을 선택해야 합이 최대가 되는가?
N, M = map(int, input().split())
atom_e = [int(input()) for _ in range(N)]
plus = [int(input()) for _ in range(M)]         # 각 에너지 준위 간의 차이값이 될 선택지인 양성자 크기 배열

max_sum = 0
for atom in atom_e:
    visited = {atom: False for atom in atom_e}                      # 모든 에너지준위에 대해 검사
    dp = {atom: [0,0] for atom in atom_e}
    dfs(atom)
    max_sum = max(max_sum,dp[atom][0], dp[atom][1])
print(max_sum)

 

시작점에서만 조사

import sys
input = sys.stdin.readline

# tree에 진입합니다.
def dfs(cur_atom):
    visited[cur_atom] = True
    dp[cur_atom][1] = cur_atom
    for gap in plus:                    # plus는 양성자크기들의 배열입니다.
        for next_atom in (cur_atom+gap, cur_atom-gap):    # 다음 노드는 지금 노드에서 양성자를 더해 갈수있는 위치입니다.
            if next_atom in visited and not visited[next_atom]:
                dfs(next_atom)
                                            # 상태인자 1은 현 노드를 가져가는 선택지, 0은 가져가지 않는 선택지입니다.
                dp[cur_atom][0] += max(dp[next_atom][1], dp[next_atom][0])      
                dp[cur_atom][1] += dp[next_atom][0]

# 각 atom_e상태가 plus를 받아들이거나 빼서 다른 atom_e에 도달할 수 있다.
# 그러나 인접한 에너지 준위가 존재하면 안된다.
# 어떤 atom_e의 조합을 선택해야 합이 최대가 되는가?
N, M = map(int, input().split())
atom_e = [int(input()) for _ in range(N)]
plus = [int(input()) for _ in range(M)]         # 각 에너지 준위 간의 차이값이 될 선택지인 양성자 크기
visited = {atom: False for atom in atom_e}                      # 모든 에너지준위에 대해 검사
dp = {atom: [0,0] for atom in atom_e}
dfs(atom_e[0])
print(max(dp[atom_e[0]][0], dp[atom_e[0]][1]))