[프로그래머스] 정수 삼각형 - ( 모든 경로 합 구해보기 )

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

 

풀이

 

def down_num(arr1,arr2):
    if len(arr1) == 1:
        for i in range(len(arr1)):
            arr.append(arr1[i]+arr2[i])
            arr.append(arr1[i]+arr2[i+1])
    else:
        for i in range(len(arr1)):
            arr.append(arr[i]+arr2[i])
            arr.append(arr[i]+arr2[i+1])
    print(arr)
    
def solution(triangle):
    global arr
    arr = []
    for i in range(len(triangle)-1):
        down_num(triangle[i],triangle[i+1])
    
    return 1

이렇게 짜면 [10,15] 이후에 [10,15,18,11,16,15] 까지는 올바르게 append 되지만 18부터가 아닌 10부터 읽어와서 그 후로는 잘못

def down_num(arr1,arr2):
    for i in range(len(arr1)):
        arr2[i] += arr1[i]
        arr2[i+1] += arr1[i]
    return arr2
    
    
def solution(triangle):
    global arr
    arr = [[i for i in j]for j in triangle]
    for i in range(len(triangle)-1):
        arr[i+1] = down_num(arr[i],arr[i+1])
    return 1

이렇게 풀면 [10,15] 다음에 4개의 값이 나와야 하는데 중간 값이 중복 합으로 계산되어버려 [18,26,15]가 되어버린다

 

 

 

def solution(triangle):
    for i in range(1,len(triangle)):
        for j in range(i+1):
            if j==0:
                triangle[i][j] += triangle[i-1][j]
            elif j==i:
                triangle[i][j]+=triangle[i-1][j-1]
            else:
                triangle[i][j]+=max(triangle[i-1][j],triangle[i-1][j-1])
    
    return max(triangle[-1])

동적 할당 풀이

sum_value = []
def down_num(triangle,value,n,i,j):
    if i == n:
        sum_value.append(value)
        return
    value += triangle[i][j]
    down_num(triangle,value,n,i+1,j)
    down_num(triangle,value,n,i+1,j+1)
    
    
def solution(triangle):
    down_num(triangle,0,len(triangle),0,0)
    
    return sum_value

재귀함수 풀이다

def find_max_path_sum(triangle, i, j):
    if i == len(triangle) - 1:
        return triangle[i][j]

    left_sum = find_max_path_sum(triangle, i + 1, j)
    right_sum = find_max_path_sum(triangle, i + 1, j + 1)

    return triangle[i][j] + max(left_sum, right_sum)

def solution(triangle):
    return find_max_path_sum(triangle, 0, 0)

이렇게도 풀 수 있다.

 

출처

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스