[프로그래머스][C++][43105] 정수 삼각형

[문제 출처]

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

1. 문제

설명

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

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

 

제한사항

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

입출력 예

 

2. 설명

 전형적인 dp문제였습니다. triangle사이즈만큼 dp벡터를 만든뒤 복사를 해주었습니다.

 

 그다음 현재위치의 값은 상단, 좌상단값중 큰 값을 현재값과 더해주는 식으로 구현하였습니다.

dp[y][x]+=max({dp[y-1][x-1], dp[y-1][x]});

 

 이때 x좌표가 0이나 맨끝좌표일때는 하나만 존재하므로

x==0일때는 상단값만 고려하는 dp[y][x]+=dp[y-1][x];

x==y일때는 좌상단값만 고려하는 dp[y][x]+=dp[y-1][x-1]; 를 예외처리해주었습니다.

 

 이중포문을 돌다가 가장 아래칸(y값이 최대일때)을 계산할때 answer안에서 max를 해주어 계속 큰값을 찾아내어 답을 찾아냈습니다. dp는 풀이는 쉽지만 생각하기가 까다롭습니다.

 

3. 코드

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

using namespace std;

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