[C++] 백준 1932번 - 정수 삼각형 (DP) 문제 풀이

백준 1932번 가장 긴 증가하는 부분 수열 문제는 여러 가지 알고리즘 중 다이내믹 프로그래밍(dp)을 사용해서 해결하는 문제이다. 규칙(점화식)을 찾으면 코드 자체는 구현하기 간단하나 규칙을 찾지 못하면 한없이 어려운 문제 유형이다. 

이 문제는 규칙이 눈에 보여서 어떻게 코드로 잘 정리하냐가 관건인 문제 같다.

 

문제 링크

 

알고리즘

 

최댓값의 경로를 파악해야 하는데 dfs 같이 모든 경로를 탐색해 버리면 n이 최대 500개라 해보진 않았지만 분명 시간 초과가 날 것 같아, 위에서 부터 한번에 돌면서 최댓값을 찾는 dp를 이용해야된 다.

 

dp 이중배열을 선언해 dp[i][j]라 하면, 위에서 부터 i번째 층에 왼쪽부터 j번째 값의 최댓값을 저장한다고 하자.

지금부터 dp배열의 값들을 구해볼 것이다. 

1. 우선 삼각형의 값들을 받아올 v배열을 이중배열(배열의 이름은 임의로 v라고 하자.)로 선언해서 이중 for문을 돌면서 입력받은 값들을 차례로 저장한다.
2. 그다음 규칙을 파악해야 하는데, 위의 예시애서, 간단하게 맨 마지막 줄을 보면 4 5 2 6 5 값들이 차례로 있다.
3. 이때 왼쪽에서 맨 첫번째 값인 4는 윗층에서 첫번째 값인 2밖 경로가 없고, 마찬가지로 마지막 값인 5도 바로 위층 맨 마지막 값인 4에서 밖에 경로가 없다.
4. 나머지 사잇값들은 각자 자신의 index -1, index 두가지 경로에서 합을 받아올 수 있다.

우리가 구해야하는 건 최댓값이 나오는 경로이므로 이것들을 일반화해 보면 i번째 층의 j번째 최댓값은

• j==0번째 index 일때는 i-1 층에서 j=0일때 dp 값이랑 본인이랑 더하는 것이고
• j==n-1번째 index 일때는 i-1 층에서 j=n-1일때 dp 값이랑 본인이랑 더하는 것이고
• 나머지는 i-1층에서 j-1번째 dp값과 j번째 dp값 중에 큰 것을 찾아 본인이랑 더하는 것이다.

그리고 마지막에 n번째 층에서 모든 dp 값 중에 최댓값을 출력한다.  

 

 

코드

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,temp;
    int res=0;
    int dp[501][500]={0,};
    cin>>n;
    int v[501][500]={0,};


    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            cin>>v[i][j];
        }
    }
    dp[1][0]=v[1][0];

    for(int i=2;i<=n;i++){
        for(int j=0;j<i;j++){
            if(j==0){
                dp[i][j]=dp[i-1][j]+v[i][j];
            }
            else if(j==i-1){
                dp[i][j]=dp[i-1][j-1]+v[i][j];
            }
            else{
                dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+v[i][j];
            }
        }
    }

    for(int i=0;i<n;i++){
        res=max(res,dp[n][i]);
    }
    cout<<res<<'\n';

    return 0;
}

//       1
//      2 3
//     4 5 6
//    7 8 9 10
//   11 12 13 14
// 15 16 17 18 19

 

제출 결과