[백준/BOJ/C++] 1932번 정수 삼각형 - Dynamic Programming

이미지를 클릭하면 문제 링크로 이동합니다.

1. 문제

    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5

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

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

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

---

2. 입력

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

---

3. 출력

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

---

4. 풀이

정수 삼각형에서 합이 최대가 되는 경로에 있는 수의 합을 구하기 위해서는 그 이전층까지의 합에 다음 층의 숫자를 더해서 계속해서 최댓값을 찾아 나가면 된다.

여기서 수를 더할 때 위의 사진처럼 삼각형의 좌측 끝과 우측 끝은 선택의 여지없이 바로 위에 있는 수를 더할 수밖에 없다.

반면, 삼각형의 양끝에 위치하지 않은 수들은 그 수에서 좌측 상단 또는 우측 상단에 있는 숫자 중 하나를 택해서 더해야 한다. 여기서 모든 경우를 구해서 마지막에 최댓값을 구하기보다는 둘 중 어떤 경우가 더 큰지 고려하여 그 숫자만을 더하는 것이 최댓값을 구하기에 효율적이다. 그리고, 계산을 할 때마다 해당 숫자가 최댓값인지를 확인하여 최종적으로 나온 최댓값을 출력해주면 된다.

---

사용 변수 : n(삼각형의 크기), max_num(최댓값 //반복문에서 갱신되는 최댓값을 저장한다.), arr(정수 삼각형과 계산 값을 저장하는 2차원 배열)

1) 먼저 삼각형의 크기를 입력받고 입력받은 크기의 2차원 배열을 생성한 다음, 정수 삼각형을 입력받는다.

2) 반복문으로 모든 숫자를 하나씩 검사하는데 이때,

1. 삼각형의 좌측 끝인 경우와 우측 끝인 경우에는 바로 위층의 각 끝의 숫자를 더해준다.
2. 삼각형의 양끝이 아닌 경우에는, 그 숫자의 대각선 왼쪽을 더하는 것과 대각선 오른쪽을 더하는 것 중 더 큰 경우를 택하여 더해준다.
3. max_num 변수에 현재 숫자가 지금까지 나온 최댓값보다 큰지 확인하여 최댓값을 변경해준다.

---

5. 소스코드

#include <iostream>
#include <string.h>
using namespace std;

int max(int a, int b){
    return a > b ? a : b;
}

int main(){
    int n; //삼각형의 크기
    cin>>n; //삼각형 크기 입력
    int max_num = 0; //반복문에서 갱신되는 최대값을 저장.

    //정수 삼각형 2차원배열 동적할당
    int **arr = new int*[n];
    for(int i = 0; i < n; i++){
        arr[i] = new int[n];
        memset(arr[i], 0, sizeof(int)*n);
    }

    //정수 삼각형 입력
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            cin>>arr[i][j];
        }
    }

    for(int i = 1; i < n; i++){
        for(int j = 0; j <= i; j++){
            if(j == 0){ //삼각형의 좌측 끝인 경우
                arr[i][j] = arr[i-1][j] + arr[i][j];
            }
            else if(j == i){ //삼각형의 우측 끝인 경우
                arr[i][j] = arr[i-1][j-1] + arr[i][j];
            }
            else{
                arr[i][j] = max(arr[i-1][j-1] + arr[i][j], arr[i-1][j] + arr[i][j]);
            }
            max_num = max(max_num, arr[i][j]);
        }
    }
    cout<<max_num;
    return 0;
}