<6주차> [BOJ / C++] 1932번 - 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

 

 

문제

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#include <cmath>
#define PI 3.141592653589793
#define ll long long

int a[505][505], d[505][505];

int main(void)
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  for(int i = 1; i <= n; ++i)
  {
    for(int j = 1; j <= i; j++)
    {
      cin >> a[i][j];
    }
  }

  d[1][1] = a[1][1];

  for(int i = 2; i <= n; i++)
  {
    for(int j = 1; j <= i; j++)
    {
      d[i][j] = max(d[i-1][j-1], d[i-1][j]) + a[i][j];
    }
  }

  cout << *max_element(d[n]+1, d[n]+n+1);
}

 

 

풀이

dp 문제이다.

테이블 정의: d[i][j] = 맨 위층에서부터 i번째 줄 j번째 수까지의 경로 중 그 합이 최대인 경우

점화식: d[i][j] = max(d[i-1][j-1], d[i-1][j])

초기값: d[1][1] = a[1][1]

 

 

결과