알고리즘/프로그래머스
Programers 정수 삼각형
내이름은 킹햄찌
2022. 3. 12. 21:51
https://programmers.co.kr/learn/courses/30/lessons/43105
코딩테스트 연습 - 정수 삼각형
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30
programmers.co.kr
프로그래머스 정수 삼각형 문제입니다.
#include <string>
#include <vector>
using namespace std;
//500 x 500 배열 선언
int dp[501][501];
int maxIdx;
int n,m;
int max(int a,int b){
return a>b?a:b;
}
int solution(vector<vector<int>> triangle) {
n = triangle.size();
m = triangle[n-1].size();
int maxIdx = 0;
if(triangle.size() == 1) return triangle[0][0];
dp[0][0] = triangle[0][0];
for(int i =1;i<triangle.size();i++){
for(int j = 0;j<=i; j++){
if(j == 0)
dp[i][j] = dp[i-1][j] + triangle[i][j];
else if(j == i){
dp[i][j] = dp[i-1][j-1] + triangle[i][j];
}
else{
dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j];
}
maxIdx = max(maxIdx, dp[i][j]);
}
}
int answer = maxIdx;
return answer;
}
아이디어
삼각형을 왼쪽으로 몰아놓고 생각을 해야함
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
탑다운 방식으로 점화식을 새워서 풀이 했는데 바텀업방식으로 풀이하면 더 깔끔 할 수 있음