프로그래머스 - 정수 삼각형(Level 3)/Wanna Be 컴잘알

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

-문제-

 

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

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

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

triangleresult

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

30

 

-설명-

 

1. dp(배열,리스트)는 각 층을 내려오면서 누적된 값을 저장하는 공간이다.

2. triangle을 한 줄씩 순회해나가면서 dp리스트를 갱신시켜주는 방식으로 만들었다.

3. triangle의 한 줄 기준 첫번째 인덱스와 마지막 인덱스는 선택의 여지가 없이 바로 위에 값을 가지고와야한다. 

4. 첫번째 인덱스와 마지막 인덱스를 제외하고 가운데에 끼어있는 인덱스들은 위에 줄의 dp[n-1], dp[n]중에 더 큰 값을 가지고 오면된다.

5. 3~4의 순서를 마지막 행까지 반복하면 DP 리스트가 완성되었을 것이다.

6. 최대값을 구해야하니 DP마지막 행의 가장 큰 값을 리턴해주면된다.

 

-코드-

 

python

def solution(triangle):
    answer = 0
    dp = [triangle[0]]
    for i,rowlst in enumerate(triangle):
        if i == 0: continue
        lst = []
        rowlength = len(rowlst)-1
        for k,in_value in enumerate(rowlst):
            if k==0:
                lst.append(dp[i-1][0]+in_value)
            elif k==rowlength:
                lst.append(dp[i-1][rowlength-1]+ in_value)
            else:
                lst.append(max(dp[i-1][k-1],dp[i-1][k])+in_value)
        dp.append(lst)

    for value in dp[-1]: answer = max(answer,value)
    
    return answer

c++

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 삼각형의 높이는 1~500이다.
// 삼각형을 이루고있는 숫 자는 1~500이다.
int dp[501][501];

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    dp[0][0] = triangle[0][0];
    dp[1][0] = dp[0][0] + triangle[1][0];
    dp[1][1] = dp[0][0] + triangle[1][1];

    for(int k=2; k<triangle.size();k++){
        dp[k][0] = dp[k-1][0] + triangle[k][0];
        dp[k][k] = dp[k-1][k-1] + triangle[k][k];
    }

    for(int k=2; k<triangle.size();k++){
        for(int i=1; i<=k-1;i++){
            dp[k][i] = max(dp[k-1][i-1],dp[k-1][i])+triangle[k][i];
        }
    }
    answer = -1;
    for(int k=0; k<triangle.size();k++){
        if(dp[triangle.size()-1][k] > answer)
            answer = dp[triangle.size()-1][k] ;
    }    
    return answer;
}