[C++] 1932번 정수 삼각형 - DP

#include <iostream>

#define MAX_SIZE 501

using namespace std;

int tri[MAX_SIZE][MAX_SIZE];  //삼각형을 저장할 2차원 배열
int MAX_tri[MAX_SIZE][MAX_SIZE];
int n;  //삼각형의 크기

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=i; j++)
            cin >> tri[i][j];
    }
    MAX_tri[1][1]=tri[1][1];  //초기값 넣어주기
    
    for(int i=2; i<=n; i++) {
        for(int j=1; j<=i; j++) {
            int Left = MAX_tri[i-1][j-1];  //왼쪽값과 오른쪽 값중 큰 것으로 저장
            int Right = MAX_tri[i-1][j];
            
            MAX_tri[i][j] = (Left>Right ? Left:Right) + tri[i][j];
        }
    }
    
    int max=0;
    for(int j=1; j<=n; j++) {  //최종 값들중(제일 아래에 있는 값) 제일 큰 값 선택
        if(MAX_tri[n][j]>max)
            max=MAX_tri[n][j];
    }
    cout << max;
    
    return 0;
}

 

오랜만에 쉬운 문제를 풀어서 너무 기분이 좋다..ㅋㅋㅋㅋ 아무튼 쉽게 풀었고

나는 8ms가 나왔는데 4ms가 나온 사람도 있어서 코드를 봤다. 그 사람은 받는 것과 MAX를 따로 계산하는 것이 아닌 받는 것과 MAX를 계산하는 것을 같이 하였다. 그러면 /2배 되겠지. 암튼 참고한 소스코드랑 사이트는 아래에 있다.

 

 

<C++ max() 함수>

https://blockdmask.tistory.com/366

[C++] 최초값, 최대값 함수 min, max 에 대해서 (클래스, vector 사용법까지)

 

<4ms 소스코드>

https://www.acmicpc.net/source/9511674

로그인

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.