백준 1932 (C++) 정수 삼각형

아이디어

처음엔 삼각형의 위에서부터 1층, ..., k층, ..., n층으로 생각하고

k층까지의 최적의 경로가 n층까지의 최적의 경로에 포함될 것이라 생각할 수도 있다.

 

그러나 예시로 주어진 테스트케이스가 그 반례이다. 

 

따라서 최적의 경로는, 2차원배열의 각 인덱스에 해당하는 dp[i][j]에 저장되어있다.

그러므로 dp[i][j]에 도달하는 optimal한 경로와 dp[i][j+1]에 도달하는 경로가 다를 것이다.

 

dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + arr[i][j];

를 사용하여 해결하면 된다.

 

다시 말하자면,
k층까지 탐색했을 때 합이 최대가 되는 것이 최적의 경로가 아니라,
k층의 l열을 오는 데에 합이 최대가 되는 경로가 최적의 경로(dp의 점화식)을 구성한다.

 

 

 

 

 

 

 

 

 

 

 

코드

#include <iostream>
using namespace std;
const int MAX = 501;
int arr[MAX][MAX];
int dp[MAX][MAX];
int sum = 0;
int main(void){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> arr[i][j];
            dp[i][j] = 0;
        }
    }
    dp[0][0] = arr[0][0];
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + arr[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        sum = max(sum, dp[n-1][i]);
    }
    cout << sum;
    return 0;
}

 

 

 

 

줄인 코드

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

const int MAX = 501;
int n, m, map[MAX][MAX] = {0, }, dp[MAX][MAX];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    int sum_max = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> map[i][j];
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + map[i][j];
            sum_max = max(sum_max, dp[i][j]);
        }
    }
    cout << sum_max;
    
    return 0;
}