백준 1932 정수 삼각형 c++ [컴공과고씨]

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

1932번: 정수 삼각형

문제 정리

             7

         3       8

      8      1      0

  2     7      4      4

처럼 삼각형이 주어짐 

이때  삼각형의 크기가 주어지는데 높이를 나타냄 

이 삼각형의 크기는 4임.

이렇게 해서 위에서 부터 숫자를 더해 밑으로 내려온다. 내려갈때는 왼쪽, 오른쪽 대각선으로 이동이 가능하다.

이때 숫자의 최대 합은?

 

문제 해결 방법

일단 다이나믹 프로그래밍을 이용해서 문제를 풀어야한다.

그리고 쉽게 문제를 풀기 위해 위 삼각형을

0 7          ------ 1번 줄

0 3 8       ------  2번 줄

0 8 1 0   -------- 3번 줄

0 2 7 4 4

이런식으로 생각해주는 것이다.

그러면 dp[i][j] 이 배열에서 i는 삼각형의 높이를 담당, j는 몇번째 숫자인지를 담당한다.

j가 0일 때는 0을 넣어준다.

그렇게 되면 윗 줄에서 밑 줄로 내려올 때 한 밑 줄에서의 j 번 칸의 최대 크기는

dp[i-1][j-1], dp[i-1][j] 이 두 개 즉, 윗 줄에 왼쪽 대각선 혹은 바로 위쪽의 값 중 큰 것을 선택하고

자신의 칸에 값을 더해주면 그 칸에 올 수 있는 최대값이 된다.

(j가 0일 때 0을 넣어준것 처럼 나머지 8위의 빈칸 이런곳들은 0으로 다 채워 넣어주면 된다.) 

 

그럼 마지막 줄에 각 칸에 최대값이 저장되어 있고 그 중 가장 큰 것을 고르면 된다.

 

전체코드

#include <iostream>
using namespace std;
int t[504][504]={0}; // 정수 삼각형 입력 받을 배열
int dp[504][504] = {0}; // 최대 합을 저장할 배열
int result = -1;
int mx(int a, int b){ // 두 수 중 큰 값을 반환하는 함수
    if(a>b)
        return a;
    else
        return b;
}
int main(){
    int n;
    cin >> n;
    int idx = 1;
    for (int i = 1; i <= n; i++){ // 정수 삼각형 입력 받음
        for (int j = 1; j <= i;j++){
            cin >> t[i][j];
        }
    }
    dp[1][1] = t[1][1]; // 맨 꼭대기 층은 같음
    for (int i = 2; i <= n; i++){ // 2번째 줄 부터 시작
        for (int j = 1; j <= i;j++){ // 1번째 칸 부터 시작
            dp[i][j] = mx(dp[i - 1][j - 1], dp[i - 1][j]) + t[i][j];
            // 윗 줄 중 바로 위쪽, 왼쪽 대각선 중 큰 것을 골라
            // 자기 칸의 값과 더함.
        }
    }
    for (int i = 1; i <= n;i++){ // 마지막 줄 중 가장 큰 것을 고름
        if(result < dp[n][i])
            result = dp[n][i];
    }
    cout << result; // 결과 출력
    return 0;
}