[DP]백준1932번 정수 삼각형

백준1932 정수 삼각형

삼각형을 배열로 나타내는 부분에서 살짝 흠칫했지만.. 종이에 한 번만 잘 그리면 쉽게 문제를 해결할 수 있는 것 같다.

DP문제는 특정 케이스를 고르지 않고 모든 경우를 저장하며 가는 케이스…라는 것을 꼭 잊지 않아야 한다.

우선 삼각형을 배열로 나타낸 것을 살펴보자.

편의상 1-index를 사용하였다.

이런 구조의 삼각형에서, 아래층으로 내려가며 선택한 수의 합이 최대가 되는 경로를 구하려면 우선 자신이 누구로부터 오는지를 알아야 한다.

문제의 조건에서

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

고 했기 때문에 경우는 두 가지로 나눌 수 있겠지만, 양쪽 끝은 오로지 한 군데로부터 올 수 밖에 없기 때문에 따로 처리를 해준다.

1. 만약 현재 줄의 첫 번째라면

   내 윗 줄의 첫 번째 원소까지의 경로의 합을 가져와 나의 값과 더한다.

    if(j==1) answer[i][j] = answer[i-1][1] + triangle[i][j];
   

2. 만약 현재 줄의 마지막이라면

   내 윗 줄의 마지막 원소까지의 경로의 합을 가져와 나의 값과 더한다.

    else if(j==i) answer[i][j] = answer[i-1][i-1] + triangle[i][j];
   

3. 그 외의 경우

   현재 내가 있는 줄을 i 번째 줄, 그 안에서의 순서를 j 번째라고 하면(왼쪽부터)

   1. 내가 있는 윗 줄의 왼쪽 원소의 값 (arr[i-1][j-1])
   2. 내가 있는 윗 줄의 오른쪽 원소의 값(arr[i-1][j])

   중 큰 값을 가져와야 한다.

    else{
         answer[i][j] = max(answer[i-1][j-1],answer[i-1][j]) + triangle[i][j];
        }
   

   이후 N 번째 줄에 도착했다면 해당 줄에서 가장 큰 값을 찾아 출력하면 된다.

    #include <iostream>
    #include <vector>
    using namespace std;
    //int arr[505][505];
    int answer[505][505];
    vector<int> triangle[505];
    int main(){
        int N;
           
        cin >> N;
        for(int i=1;i<=N;i++){
            vector<int> tmp;
            tmp.push_back(0);
            for(int j = 1; j <= i; j++){
                   
                int tmpp;
                cin >> tmpp;
                tmp.push_back(tmpp);
            }
            triangle[i] = tmp;
        }
           
        answer[1][1] = triangle[1][1];
        answer[2][1] = triangle[1][1] + triangle[2][1];
        answer[2][2] = triangle[1][1] + triangle[2][2];
           
        for(int i=3;i<=N;i++){
            for(int j=1;j<=i;j++){
                if(j==1) answer[i][j] = answer[i-1][1] + triangle[i][j];
                else if(j==i) answer[i][j] = answer[i-1][i-1] + triangle[i][j];
                else{
                    answer[i][j] = max(answer[i-1][j-1],answer[i-1][j]) + triangle[i][j];
                }
            }
        }
        int tmp = answer[N][1];
        for(int i=1;i<=N;i++){
            if(answer[N][i] > tmp) tmp = answer[N][i];
        }
        cout << tmp << "\n";
    }