프로그래머스 문제 - 정수 삼각형

프로그래머스 정수 삼각형 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

500 이하의 높이를 가진 정수 삼각형이 주어집니다.
위의 숫자는 아래의 좌,우로 이동이 가능합니다.
맨 윗줄 부터 마지막 줄까지 움직일 때 거쳐간 숫자들의 합의 최대값을 알아야합니다.

문제 풀이

위에서부터 차례대로 수를 더하며 제일 아래까지 도달했을 때 지나간 수들의 최대값을 구해야 합니다.
삼각형의 크기가 500으로 많지 않기 때문에 두번째줄부터 양쪽 위의 숫자들을 비교하여 큰 수를 마지막 줄까지 더해주면 됩니다.

for(int i = 1; i < triangle.size(); i++)
{
    for(int j = 0; j < i + 1; j++)
    {
        //맨 왼쪽과 오른쪽의 수는 바로 더해주기
        //그외의 수는 위의 두 값을 비교하여 더 큰 수를 입력함
        if(j == 0)
        {
            triangle[i][j] += triangle[i-1][j];
        }
        else if(j == i)
        {
            triangle[i][j] += triangle[i-1][j-1];
        }
        else
        {
            int left = triangle[i][j] + triangle[i-1][j-1];
            int right = triangle[i][j] + triangle[i-1][j];
            left > right ? triangle[i][j] = left : triangle[i][j] = right;
        }
    }
}

제일 큰 숫자를 구해야 하기 때문에 sort를 사용하여 정렬 후 배열의 마지막 숫자가 제일 큰 수가 됩니다.

전체 코드

이번 문제는 내용만 잘 이해하면 풀 수 있는 문제였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    
    for(int i = 1; i < triangle.size(); i++)
    {
        for(int j = 0; j < i + 1; j++)
        {
            //맨 왼쪽과 오른쪽의 수는 바로 더해주기
            //그외의 수는 위의 두 값을 비교하여 더 큰 수를 입력함
            if(j == 0)
            {
                triangle[i][j] += triangle[i-1][j];
            }
            else if(j == i)
            {
                triangle[i][j] += triangle[i-1][j-1];
            }
            else
            {
                int left = triangle[i][j] + triangle[i-1][j-1];
                int right = triangle[i][j] + triangle[i-1][j];
                left > right ? triangle[i][j] = left : triangle[i][j] = right;
            }
        }
    }
    
    //맨 아래의 제일 큰 수를 정렬하여 찾아냄
    sort(triangle[triangle.size()-1].begin(), triangle[triangle.size()-1].end());
    answer = triangle[triangle.size()-1][triangle.size()-1];

    return answer;
}

출저

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