프로그래머스. 정수 삼각형

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

프로그래머스

 

전체 코드

한승협님 코드

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

    return max(tri[-1])

 

위에서부터 양쪽으로 더해나간다. 삼각형의 양끝이 아니면 중첩되는 부분이 있다. 해당 부분을 max를 통해 더 큰 값을 더하도록 한다.

 

내가 작성한 코드 

def solution(triangle):
    for idx in range(len(triangle) - 1):
        cur = triangle[idx]
        next = triangle[idx + 1]
        temp = [0] * len(next)

        for i in range(len(cur)):
            temp[i] = max(temp[i], next[i] + cur[i])
            temp[i + 1] = max(temp[i + 1], next[i + 1] + cur[i])

        triangle[idx + 1] = temp

    return max(triangle[-1])

temp 변수를 사용하여 max값을 계산한 후 next에 갈아 끼운다. 위의 코드에 비해 항상 max값을 계산하고 temp 배열을 생성해야하기 때문에 효율이 좋지 않다. 위의 코드처럼 작성할 수 있도록 한다.