[백준] 1932번: 정수 삼각형 풀이 및 해설(C++)

문제 이미지

 

풀이

피라미드 형태의 문제 그대로 배열을 만들면 된다.

n에는 높이, m에는 수평개수가 들어가는 arr [n][m] 배열을 만든다. 

n에는 높이, m에는 수평개수가 들어가는 dp[n][m] 배열도 만든다.

dp [0][0]에 점화식을 위한 처음값 arr [0][0]을 넣어준다.

그리고 dp[n][m]에 dp [n-1][m]과 dp [n-1][m-1] 중 큰 값을 고르고 arr [n][m]을 더해 할당한다.

이때 인덱스가 최소 최대 범위를 넘지 않도록 조심한다.

그리고 마지막 dp[n]에서 배열들 중 최댓값을 출력한다. 

 

 

해답 코드

#include <iostream>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int main(){
    fastio;
    int n,maxi;
    cin>>n;
    int arr[501][501]={0};
    int sum[501][501]={0};
    cin>>arr[0][0];
    sum[0][0]=arr[0][0];
    for(int i=1; i<n; i++){
        for(int j=0; j<i+1; j++){
            cin>>arr[i][j];
        }
        sum[i][0]=sum[i-1][0]+arr[i][0];
        //피라미드의 가장 왼쪽은 선택지가 없으니 따로 빼서 계산
        for(int j=1; j<i; j++){
            sum[i][j]=arr[i][j]+max(sum[i-1][j],sum[i-1][j-1]);
        }
        sum[i][i]=sum[i-1][i-1]+arr[i][i];
        //피라미드의 가장 오른쪽 역시 선택지가 없으니 따로 빼서 계산
    }
    maxi=sum[n-1][0];
    for(int i=1; i<n; i++){
        if(maxi<sum[n-1][i]){
            maxi=sum[n-1][i];
        }
    }
    cout<<maxi;

}

해당 문제풀이를 할때는 dp 이름을 sum이라고 썼다.