3. 정수 삼각형

    3번 문제   

 

---

    내가 풀이한 답   

 

 Bottom-up 방식으로 접근하였고 2번 알리바바와 40인의 도둑과 매우 비슷한 유형의 문제라고 생각했다. 정수 삼각형 역시 경우의 수를 생각해 보았다. 

 

 첫 번째는 보라색 부분과 같이 오른쪽 대각선으로만 올 수 있는 경우였다. 이는 대각선 방향의 왼쪽값과 해당 위치의 값을 더해주었다.

 

 두 번째는 하늘색 부분가 같이 왼쪽 대각선으로만 올 수 있는 경우였다. 이는 위쪽 값과 해당 위치의 값을 더해주었다.

 

 마지막으로는 오른쪽과 왼쪽 대각선으로 둘 다 올 수 있는 경우였다. 이는 대각선 방향의 왼쪽값과 위쪽 값 중 제일 작은 값과 해당 위치의 값을 더해주었다.  

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

 

 

 결과는 통과하였다.

 

---

    다른 사람들의 풀이   

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {

    //바닥부터 큰 값의 수를 윗 칸에 더해나간다
    for(int i = triangle.size()-2; i > -1; i--){
        for(int j = 0; j <= i; j++){
            triangle[i+1][j] > triangle[i+1][j+1] ? triangle[i][j] += triangle[i+1][j] : triangle[i][j] += triangle[i+1][j+1];
        }
    }

    return triangle[0][0];
}

 

 제일 끝 부분부터 큰 값의 수를 더해간다는 것이 인상 깊었다. 전혀 생각지도 못한 풀이였다.