[Programmers] Level 3. 정수 삼각형 (Python)

🔗 Problem Link

프로그래머스

---

❔Thinking

• 삼각형 상단에서 바닥까지 차례대로 내려오면서, 각 숫자를 더해나간다.
• 대각선 왼쪽과 오른쪽으로만 내려올 수 있다.
• 가장 큰 수를 만들 수 있는 경로로 내려왔을 때, 그 합을 반환한다.

---

💻Solution

1. 위에서 아래로 내려오면서 더해나가는 풀이

def solution(triangle):
    if len(triangle) == 1:
        return (triangle[0])
    while len(triangle) > 1:
        sum_result = []
        max_result = []
        # 상단 두줄 꺼내기
        up, down = triangle.pop(0), triangle.pop(0)
        # 더하기
        for i in range(len(up)):
            sum_result += [up[i]+down[i], up[i]+down[i+1]]
        # 두 개씩 max()하기
        for i in range(1, len(sum_result)-1, 2):
            max_result.append(max(sum_result[i], sum_result[i+1]))
        # 삼각형에 합치기
        max_result = [sum_result[0]] + max_result + [sum_result[-1]]
        triangle = [max_result] + triangle
    return max(*triangle)

 

2. 아래서 위로 올라가면서 더해나가는 풀이 (출처 - 프로그래머스 다른 사람의 풀이)

def solution(triangle):
    height = len(triangle)
    while height > 1:
        for i in range(height - 1):
            triangle[height-2][i] += max([triangle[height-1][i], triangle[height-1][i+1]])
        height -= 1
    answer = triangle[0][0]
    return answer

---

🗝️keypoint

1. 위에서 아래로 더해가는 풀이의 경우, 양 끝을 제외하고 두자리씩 max()를 하여 새로운 층을 만들어야 한다.
2. 모든 경로를 탐색하여 최대값을 찾는 경우, 삼각형의 높이가 높아지면 시간이 많이 걸린다.