[백준 1932번 C++] 정수 삼각형

1932번: 정수 삼각형 (acmicpc.net)

1932번: 정수 삼각형

---

 

위 예시의 삼각형을 아래처럼 입력을 받는다

 

[풀이]

가장 아랫줄부터 시작해서 올라가는 방식인 데,

가장 아랫줄에 인접한 두 원소 중 큰 원소를 대각선 위의 원소와 합하는 것을 반복한다

ex) 4번째 줄의 2는 2+ max(4, 5) = 7로 바뀐다

4번째 줄의 7은 7+ max(5, 2) = 12로 바뀐다

4번째 줄의 4는 4+ max(2, 6) = 10으로 바뀐다

4번째 줄의 4는 4+ max(6, 5) = 10 으로 바뀐다

 

그럼 삼각형은 이렇게 바뀜. 그 아랫줄은 이제 신경 쓰지 않는다

7
3 8 
8 1 0 
7 12 10 10 

이를 반복해보면

7
3 8
20 13 10

7
23 21

30

 

[참고]

[ C / C++ ] 백준 1932 정수 삼각형 (tistory.com)

[ C / C++ ] 백준 1932 정수 삼각형

---

이를 코드로 표현해보자!

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;
    
    int tri[n][n];
    
    //삼각형 입력 받기
    for(int i=0; i<n; i++){
        for(int j = 0; j<=i; j++){
            cin >> tri[i][j];
        }
    }
    
    //풀이: 가장 아랫줄부터 시작해서 삼각형을 수정해나감
    for(int i=n-1; i>0 ; i--){
        for(int j=0; j<i; j++){
            tri[i-1][j] += max(tri[i][j], tri[i][j+1]);
        }
    }
    
    cout <<  tri[0][0] <<"\n";
    
    return 0;
}