백준1932 정수삼각형

2021.06.12 정수삼각형

Solution

• DFS : 삼각형의 꼭대기에서부터 아래 or 오른쪽아래로 깊이우선탐색을 합니다.

  DFS로 탐색을 구현할 때 리턴하는 값은 다음과 같이 설정할 수 있습니다.

  • 맨 아래인 경우 : 해당 노드의 값
  • 맨 아래가 아닌 경우 : 해당 노드의 값 = 그 다음노드부터 맨 아래까지의 최대경로

  이렇게 설정하면 결국 재귀로 구현한 깊이우선탐색의 최종 반환 값이 원하는 결과가 됩니다.

• DP : 위의 DFS에서 각 노드를 탐색할 때, 이미 탐색한 적이 있는 경우 메모이제이션 을 활용할 수 있습니다.

  해당 노드부터 맨 아래까지의 경로 중 최댓값을 DP 배열에 저장하고, 이미 탐색한 적이 있는 경우 (DP 배열이 초기값이 아닌경우) 에는 메모이제이션 해둔 값을 반환하도록 합니다.

Source

# DP
# 2021.06.12

def getResult(input_map, memo, y, x, N):
    # DP
    if memo[y][x] != -1:
        return memo[y][x]
    # bottom
    if y >= N-1:
        return input_map[y][x]

    # DFS
    memo[y][x] = input_map[y][x] + max(getResult(input_map, memo, y+1, x, N), getResult(input_map, memo, y+1, x+1, N))

    return memo[y][x]

N = int(input())
my_map = []
memo = [[-1 for _ in range(n)] for n in range(1, N+1)] # max route from this node to bottom

for n in range(N):
    my_map.append(list(map(int, input().split())))

print(getResult(my_map, memo, 0, 0, N))