프로그래머스 43105 - 정수 삼각형 (c++)

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

문제 링크

생각 및 접근

• 정수 삼각형을 배열 형태로 숫자를 작성해보면 다음과 같다.
  

  

• 삼각형의 맨 윗 층부터 내려오면서, vector<vector<int>> t에 t[i][j]까지 검사했을 때, 최댓값이 들어오게끔 DP 방식 코드를 짜고자 했다.
• 검사하는 방식은 이렇다.
  

  

  • 화살표를 하나만 받는 원소와 화살표를 두 개 받는 원소를 나눴다.
    • 화살표 하나만 받는 원소 : 각 층의 양 끝
    • 화살표 두 개 받는 원소 : 양 끝을 제외한 나머지
      • max 함수를 사용해서 두 가지중 큰 것을 t[i][j]에 더해주면 된다.

코드

#include <bits/stdc++.h>
using namespace std;

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

    int answer = -1;
    for(auto d : t[t.size() - 1]){
        if(d > answer)  answer = d;
    }
    return answer;
}

채점 결과