프로그래머스 lv 3. 43105 정수 삼각형 c++ **다시 풀어보기**

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

#include <bits/stdc++.h>

using namespace std;

int d[505][505];

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int n=triangle.size();
    d[1][1]=triangle[0][0];
    for(int i=2; i<=n; i++)
        for(int j=1; j<=i; j++)
            d[i][j]=max(d[i-1][j-1],d[i-1][j]) +triangle[i-1][j-1];//d[i-1][0] 의 경우 0
    answer=*max_element(d[n]+1,d[n]+n+1);
    return answer;
}

 

위의 방법은 1-indexed 를 기준으로 잡을때, 전역변수로 선언한 d에서 모든 원소가 0으로 초기화 된다는걸 이용한

형태의 코드이고 그렇기 때문에 예외처리를 따로 해주지 않아도 되는 형태이다. 

 

위에서 아래로 내려가는 형태로 계속 값을 갱신해가는 형태로 작성했으며, 정수삼각형에서 각 삼각형을 이루는 정수로 도착했을때의 최대값을 각각의 배열 d에 저장하는 형태로 dp를 활용한 풀이이다. 

 

그런데 다른 사람의 풀이를 보니까 아주 재미있는 풀이를 발견해서 첨부한다. 

역방향으로 아래에서 위로 올라가는 형태로 작성하면 배열 d를 새로 선언해서 값을 저장하는것 보다 

주어진 t의 값들을 변경해가면서 올라가서 t[0][0]에 가장 큰 값이 담기게 하는 풀이이다. 

 

#include <bits/stdc++.h>

using namespace std;

int solution(vector<vector<int>> t) {
    int answer = 0;

    for (int i = t.size() - 1; i > 0 ; i--){
        for (int j = 0; j < t[i].size() - 1; j++){
            (t[i][j] > t[i][j + 1]) ? t[i - 1][j] += t[i][j] : t[i-1][j]+=t[i][j+1];
        }
    }
    answer = t[0][0];
    return answer;
}

 

if(t[i][j] > t[i][j+1]) t[i-1][j] += t[i][j];
else t[i-1][j] += t[i][j+1];

위와 같은 코드로 2중 for 문 속에 작성할 수 있는 코드인데, 더 간략해 보이기 위해 삼항연산자를 활용했다

 

이때 중요한 것은, 아래에서 두개의 항중에서 더 큰 값을 자신의 위 칸으로 삼각형을 이루는 항으로 합쳐 올릴것이기 때문에, j의 경우 맨 마지막 항 바로 전 항까지만 for문에서 판별한다. 그래서 for(int j=0; j<t[i].size()-1; j++) 의 범위가 된다. 

 

이 풀이 아주아주 멋진것 같다. 훌륭하다.