[Python] 프로그래머스 - 정수 삼각형

Programmers 정수 삼각형

풀이

def solution(triangle):
    answer = 0
    
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            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-1], triangle[i-1][j])
    
    answer = max(triangle[-1])
    
    return answer

동적 계획법 (DP, Dynamic Programming)

큰 문제를 작은 문제들로 나누고, 이미 구한 작은 문제의 답을 저장해서 다시 사용하는 방식

• 매번 처음부터 다시 계산하지 않고, 이미 구한 결과를 저장해두고 재사용하는 방법

• 동적 계획법을 이용해서 위 문제 풀이를 진행하면서, ‘이 칸까지 도착했을 때 얻을 수 있는 최대 합’을 구하기 위해 triangle[i][j] = 맨 위에서 이 칸까지 오는 최대 합으로 triangle[i][j]의 의미를 바꿈

• 자바에서도 동일하게 구현할 수 있음

    class Solution {
        public int solution(int[][] triangle) {
            for (int i = 1; i < triangle.length; i++) {
                for (int j = 0; j < triangle[i].length; j++) {
  
                    if (j == 0) {
                        // 왼쪽 끝: 바로 위에서만 내려올 수 있음
                        triangle[i][j] += triangle[i - 1][j];
                    } 
                    else if (j == i) {
                        // 오른쪽 끝: 왼쪽 위에서만 내려올 수 있음
                        triangle[i][j] += triangle[i - 1][j - 1];
                    } 
                    else {
                        // 가운데: 왼쪽 위, 오른쪽 위 중 더 큰 값 선택
                        triangle[i][j] += Math.max(triangle[i - 1][j - 1], triangle[i - 1][j]);
                    }
                }
            }
  
            int answer = 0;
  
            for (int i = 0; i < triangle[triangle.length - 1].length; i++) {
                answer = Math.max(answer, triangle[triangle.length - 1][i]);
            }
  
            return answer;
        }
    }