JArchive 프로그래밍 일기

정수 삼각형 문제 링크 

리뷰 

등굣길 문제와 비슷하게 느껴졌다. 

삼각형의 가로 세로는 500이하라는 조건이 있으니까 점화식 값을 저장할 DP배열 크기를 501, 501로 잡아둔다. 

최대 합을 구하려면, 반드시 1층부터 마지막층까지 이동해야 한다. 

모든 층의 첫번째 칸은 바로 위에서만 올 수 있다. 

모든 층의 마지막 칸은 왼쪽 위에서만 올 수 있다. 

이 2가지 예외를 제외하고, 아래와 같은 점화식을 만족한다. 

D[a][b] = max(D[a-1][b] , D[a][b-1]) + 현재칸의 값 A[a][b]

맞았습니다 코드 

#include <string>
#include <vector>
using namespace std;

int D[501][501];

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

  D[0][0] = t[0][0];
  D[1][0] = t[1][0] + D[0][0];
  D[1][1] = t[1][1] + D[0][0];

  int height_t = t.size();

  for(int i = 2; i < height_t; i++){

    for(int j = 0; j <= i; j++){
      if(j == 0) D[i][j] = t[i][j] + D[i-1][j];
      else if(j == i) D[i][j] = t[i][j] + D[i-1][i-1];
      else{
        D[i][j] = t[i][j] + max(D[i-1][j], D[i-1][j-1]);
      }
    }
  }

  for(int i = 0; i < height_t; i++){
    answer = max(answer, D[height_t-1][i]);
  }

  return answer;
}