문제 설명
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 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
첫 번째 시도
알고리즘
그림에 나와있는 삼각형들을 쪼개 봤을 때, 이전에 나온 최댓값을 따라간다고 꼭 최댓값이 나오는게 아니기 때문에, 어쨋든 끝까지 내려가야한다고 생각을 해서, DFS 방식으로 코드를 짯다.
재귀함수를 호출하여서, 삼각형의 끝까지 내려가면 합산된 값을 return 받아서 비교하는 방식의 코드이다.
실행 코드
maxx = 0
def dp(triangle,i,j,sum):
global maxx
tlen = len(triangle)
if i >= tlen: # 삼각형 끝까지 탐색 끝남.
return sum
sum += triangle[i][j]
maxx = max(dp(triangle,i+1,j,sum),dp(triangle,i+1,j+1,sum),maxx)
return sum
def solution(triangle):
global maxx
tlen = len(triangle) # 삼각형 세로 길이. 주석의 i라고 할 수 있다. 0~tlen-1 까지.
dp(triangle,0,0,0)
answer = maxx
return answer실행 결과
실행 결과를 보니 아마도 코드 자체에는 이상이 없으나, DFS방식이다보니 시간복잡도가 O(N+E) 이라서 시간 초과가 뜨는 것 같다.
두 번째 시도
알고리즘
코드를 여러차례 수정해 보았으나, 아무리 효율적으로 짜도 시간 복잡도를 개선하는데에는 한계가 있었다. 그래서 구글링을 하여 참고를 해보았다.
triangle[i][j] += max(triangle[i-1][j], triangle[i-1][[j-1])
위에 식처럼, 삼각형의 각 지점에 거쳐간 숫자의 합이 최대인 경우만 저장해 놓고, 아래로 계속 내려가면 시간 복잡도가 O(N)이 나오기 때문에, 훨씬 더 효율적인 코드를 짤 수 있다.
물론 j=0, j=i, i=0, i=1 일때 예외처리는 확실히 해줘야 한다.
정답 코드
def solution(triangle):
tlen = len(triangle) # 삼각형 세로 길이. 주석의 i라고 할 수 있다. 0~tlen-1 까지.
for i in range(1,tlen):
if i == 1: # i = 1 은 그냥 더하기 밖에 안함.
triangle[1][0] += triangle[0][0]
triangle[1][1] += triangle[0][0]
else:
for j in range(0,i+1):
if j == 0: # j = 0 일 때, j-1은 존재하지 않는다.
triangle[i][j] += triangle[i-1][j]
elif j == i: # j=i일 때, [i-1][j]는 존재하지 않는다.
triangle[i][j] += triangle[i-1][j-1]
else:
triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])
answer = max(triangle[tlen-1])
return answer결과는 성공! 레벨 3치고는 쉬웠던 것 같다.
