프로그래머스 43105 정수삼각형 c++ // dp , 인덱스에 주의하자, 일반식을 정확하게 짜는방법

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

프로그래머스

1. 일반식을 정확하게 짜는방법

오류 : if(j==i)우측 끝일때 d[i][j]=d[i-1][i]

해결 : if(j==i)우측 끝일때 d[i][j]=d[i-1][i-1]

아래그림에서 d[0위치]=d[8위치]==d[i-1][i-1]이 되어야한다!

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;

int dp[504][504];

//1. d[i][j] : i높이에서 누적 최대합. / j번째 행에서

//d[0]=7
//d[1][0]=7+3
//d[1][1]=7+8

//d[2][0]=d[1][0]+score[2][0]
//d[2][1]=max(d[1][0], d[1][1])+score[2][1]
//d[2][2]=d[1][1]+score[2][2]

//2. d[i][j] = max(d[i-1][j-1],d[i-1][j])+score[k][i]
//단, i==0 -> d[i][j] =d[i-1][0]+score[i][j]
//단, i==n끝 -> d[i][j] =d[i-1][끝]+score[i][j]
//여기가 j-1이 되어야함!!!!!!!!!!!!!!
int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int n = triangle.size();
    dp[0][0] = triangle[0][0];
    for(int i = 1; i<n; i++){
        for(int j = 0; j<=i; j++){
            if(j==0) dp[i][j] = dp[i-1][0] + triangle[i][j];
            else if(j==i) dp[i][j] = dp[i-1][i-1] + triangle[i][j];
            else{
                dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        }
    }
    
    return *max_element(dp[n-1],dp[n-1]+n);
    
}