정수 삼각형
문제 설명
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
제한사항
- 삼각형의 높이는 1 이상 500 이하입니다.
- 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
입출력 예
triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30
concept
-
마지막에 어떤 큰 값(변수)가 있을지 모르므로 마지막까지 모두 탐색을 해봐야한다.
-> 진행하면서 항상 최적의 값을 찾을 수가 없다는 이야기.. -
dfs로 탐색하여 최솟값을 구할 수도 있음
-
bfs로 탐색하기에는,, 위와 같은 케이스때문에 효율적으로 보이진 않음..
-
진행하면서 누적값을 저장하여 가장 마지막까지 진행한 후 마지막에서 최솟값을 뽑아내는것이 효율적
->누적값을 저장하면서 진행하기에 dp의 대표적 예제..
code
def solution(triangle):
answer = 0
parent = triangle[0]
for row in triangle:
#꼭대기 스킵
length = len(row)
if(length==1):
continue
for i in range(length):
if(not i):
row[i] += parent[i]
elif(i == length-1):
row[i] += parent[i-1]
else:
row[i] += max(parent[i], parent[i-1])
parent = row
return max(triangle[-1])참고
- 인덱스로 접근하여 0번째 인덱스를 Skip할 수도 있음..
hello