[프로그래머스] - 정수 삼각형(C/C++)

프로그래머스

[문제 설명]

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

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

제한사항

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

입출력 예

 

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

---

[문제 풀이]

이 문제는 DP 메모이제이션을 이용해서 풀어야한다.

현재까지의 값을 계산해서 계속해서 저장해나가야한다.

위 입출력 예로 설명해보자면,

[7]

[3,8]

[8,1,0]

[2,7,4,4]

[4,5,2,6,5]

위와 같이 되어있다.

 

문제 설명을 읽어보면 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다.  이라는 조건이 있다.

 

거꾸로 생각해서 아래칸에서 윗칸으로 본다고 가정하면, 각 줄의 첫번째와 마지막 숫자는 그 전 줄의 첫번째와 마지막 숫자와만 연산이 가능하다.

 

2번째줄 3의 경우에는 7, 8의 경우에도 7

3번째줄 8의 경우에는 3, 0의 경우에는 8

4번째줄 2는 8, 4는 0 ...

위와 같은 규칙이 있다.

 

나머지는 왼쪽 대각선, 오른쪽 대각선 중 더 큰값을 고르면 된다.

 

아래의 과정은 매 줄 마다  연산된 결과를 보여준다.

 

1.

[7]

[3,8]

[8,1,0]

[2,7,4,4]

[4,5,2,6,5]

 

2.

[7]

[10,15] (7 + 3, 7 + 8)

[8,1,0]

[2,7,4,4]

[4,5,2,6,5]

 

3.

[7]

[10,15]

[18,16,15] (8 + 10, 1 + 15, 0 + 15)

[2,7,4,4]

[4,5,2,6,5]

 

4.

[7]

[10,15]

[18,16,15]

[20,25,20,19] (2 + 18, 7 + 18, 4 + 16, 4 + 15)

[4,5,2,6,5]

 

5.

[7]

[10,15]

[18,16,15]

[20,25,20,19]

[24,30,27,26,24] (4 + 20, 5 + 25, 2 + 25, 6 + 20, 5 + 19)

 

마지막 줄에서 가장 큰 값을 answer에 저장하여 리턴하면 된다.

[코드]

[GitHub]

GitHub - EGyeom/ProblemSolving

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = -1;
    int triangleSize = triangle.size();
    
    for(int i = 1; i < triangleSize; i++)
    {
        for(int j = 0; j <= i; j++ )
        {
            if(j == 0)
            {
                triangle[i][j] = triangle[i][j] + triangle[i-1][j];
            }
            else if(j == i)
            {
                triangle[i][j] = triangle[i][j] + triangle[i-1][j-1];
            }
            else
            {
                triangle[i][j] = triangle[i][j] + max(triangle[i-1][j-1], triangle[i-1][j]);
            }
            
            if(i == triangleSize-1)
                answer = max(answer, triangle[i][j]);
        }
    }
    
    return answer;
}