# [알고리즘 C++] 정수 삼각형

huijae0817·2020년 9월 30일
1

목록 보기
61/117

## 오늘의 문제

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

### 나의 풀이

#include <string>
#include <vector>

using namespace std;

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

vector<vector<int>> dp = triangle;
for(int i=0;i<triangle.size()-1;i++){
for(int j =0;j<triangle[i].size();j++){
dp[i][j] = -1;
}
}
dp[0][0] = triangle[0][0];

for(int i=0;i<triangle.size()-1;i++){
for(int j =0;j<triangle[i].size();j++){
int up = dp[i][j];
dp[i+1][j] = max(dp[i+1][j], up + triangle[i+1][j]);//왼
dp[i+1][j+1] = max(dp[i+1][j+1], up + triangle[i+1][j+1]);//오
}
}
for(int i=0;i<dp[dp.size()-1].size();i++)
}

### 모범 답안

#include <string>
#include <vector>

using namespace std;

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

int temp;
int Size = triangle.size();
for (int i = 0; i < Size; ++i)
{
temp = 0;
if (i != Size - 1)
{
for (int j = 0; j < triangle[i].size(); ++j)
{
if (temp < triangle[i + 1][j] + triangle[i][j])
temp = triangle[i + 1][j] + triangle[i][j];

triangle[i+1][j] = temp;
if (j != triangle[i].size() - 1)
temp = triangle[i + 1][j + 1] + triangle[i][j];
else
triangle[i + 1][j + 1] += triangle[i][j];
}
}
else if (i == Size - 1)
{
for (int j = 0; j < triangle[i].size(); ++j)
{
}
}
}

}