[코딩테스트 스터디/C++] 백준 1932번 정수삼각형

1.문제 링크

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

2. 풀이 전 계획과 생각

• 다이나믹 프로그래밍 하기

3. 풀이

#include<iostream>
using namespace std;

int n;

int a[501][501];
int d[501][501];

int main(){
	// 입력  
    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=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            d[i][j]=d[i-1][j];
            if(d[i][j]<d[i-1][j-1]) d[i][j]=d[i-1][j-1];
            d[i][j]+=a[i][j];
        }
    }
    
    // 가장 아래층 중에서 최댓값을 정답으로 갱신  
    int ans=d[n][1];
    for(int i=1;i<=n;i++){
        if(ans<d[n][i]) ans=d[n][i];
    }
    
    // 답 출력  
    cout<<ans;
}

1. 1층은 d[1][1] = a[1][1]로 초기화
2. 1~N층까지 M층에 대해서 d[M][j]에 대해 d[M-1][j]와 d[M-1][j-1] 중 더 큰값으로 초기화
3. d배열의 N행 중 최댓값이 정답

4. 풀이하면서 고민했던 점

• 없음

5. 문제를 풀고 알게된 개념 및 소감

• 다이나믹 프로그래밍에 개념에 대해 잘 알게됨