[프로그래머스] 코딩테스트 연습 > 동적계획법(Dynamic Programming) > 정수 삼각형 (C++)

// c++
#include <bits/stdc++.h>
using namespace std;

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

    vector< vector<int> > d(510, vector<int>(510, 0));

	// triangle 배열의 데이터를 d 배열에다가 붙여넣기
    for (int i = 0; i < triangle.size(); i++) {
        for (int j = 0; j < triangle[i].size(); j++)
            d[i][j] = triangle[i][j];
    }

	// 점화식 세운 것을 기반으로 반복문 돌리기
    
    for (int i = 0; i < triangle.size(); i++) {
        for (int j = 0; j < triangle[i].size(); j++)
        {
            if (i - 1 < 0) d[i][j] = triangle[i][j]; // i=0, j=0 인 경우
            else if (i - 1 >= 0 && j - 1 < 0) d[i][j] = d[i - 1][j]+triangle[i][j]; // j=0 인 경우
            else d[i][j] = max(d[i - 1][j - 1], d[i - 1][j]) + triangle[i][j]; // 나머지 경우
        }
    }

	// 마지막 줄의 데이터 중 가장 큰 값 return 하기
    int lastRow = triangle.size() - 1;
    for (int i = 0; i < d[lastRow].size(); i++) {
        answer = max(answer, d[lastRow][i]);
    }
    
    return answer;
}

---

※ 점화식 세우기

 

→ 주어진 배열을 가지고 2차원 배열을 형성했을 때,

(i,j)에 올 수 있는 숫자의 최댓값은, (i-1,j-1)과 (i-1,j)의 최댓값에 (i,j)의 현재 값을 더하는 것이다.

 

 

※ 고민했던 부분 1

 

→ 2차원 벡터 복사해서 붙여넣는 문제 : 그냥 넉넉하게 배열 크기 할당해서, 2중 반복문 돌면서 붙여넣기 하자!

 

 

※ 고민했던 부분 2

 

→ 점화식 기반으로 반복문 돌릴 때, i-1 나 j-1 이 0 보다 작을 때의 조건문 처리