정수 삼각형

 

 

유형 분석

이 문제 또한 전에 풀었던 금광문제처럼 사고의 전환이 필요하다.

1열에서 2열로 더한다 라기 보단

2열을 기준으로 1열에서 최선의 선택을 해 더한다로 생각하는게 낫다.

 

다만, 헷갈렸던 점은 대각선을 더해야하는데, 2차원 배열로 나타내면 대각선 표현이 어렵다는 점이다.

그걸 주의해서 잘 풀어야 하는것 같다.

 

 

코드

 

n = int(input())
m = int(input())
graph = []
graph.append([m])
for i in range(1, n):
    graph.append(list(map(int, input().split())))

dy = [-1, 0]
for x in range(1, n):
    for y in range(len(graph[x])):
        max_value = 0
        for i in range(2):
            before_x = x-1
            before_y = y+dy[i]
            if before_y < 0 or before_y >= len(graph[x-1]):
                continue
            max_value = max(max_value, graph[before_x][before_y])
        graph[x][y] = max_value + graph[x][y]

result = 0
for i in range(len(graph[-1])):
    result = max(result, graph[-1][i])
print(result)