[Algorithm] 백준 1932번 : 정수 삼각형 (C++)

문제 링크 : https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

---

[문제]

정수 삼각형

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

[입력]

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

[출력]

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

[알고리즘 분류]

• 다이나믹 프로그래밍

---

[해설]

문제의 설명을 보면 이 문제는 주어진 값을 가지고 특정 위치에서 시작하여 끝까지 값을 중복해 나가 정답을 구하는 문제임을 알 수 있다.
문제에서는 위에서부터 내려오면서 수의 합이 최대가 되는 경로를 구한다고 하고있지만 코드를 이와 같이 작성할 경우 n의 크기가 커질 수록 아래층에서의 분기점이 많아지게 되어 계산 과정이 복잡하게 될 것이다.

하지만, 정수 삼각형의 아래에서 두 숫자끼리 비교해가며 더 큰 수를 윗 층의 숫자에 중복해 나가는 방식으로 풀게되면 복잡한 비교 과정이 단순하게 변하게 된다.

문제에서 주어진 예시로 표현해보자면 다음과 같이 나타낼 수 있는 것이다.

아래에서부터 좌우의 숫자들을 비교해 큰 값을 위로 더하여 나간다.

[정답 코드]

#include<bits/stdc++.h>
using namespace std;
int n, M[501][501];

int main(){
	scanf("%d",&n);
    
	for(int i=0;i<n;i++) 
      for(int j=0;j<i+1;j++) 
        scanf("%d",&M[i][j]);
    
	for(int i=n-1;i>=1;i--) 
      for(int j=0;j<i;j++) 
        M[i-1][j] += max(M[i][j],M[i][j+1]);
        
	printf("%d",M[0][0]);
}

[결과]