1932

백준 1932번

Link: 1932번: 정수 삼각형

---

문제 설명

어제 풀었던 RGB거리와 비슷한 유형의 DP 문제.

다른점이 있다면 제한조건인데, 3가지 경우를 고려했어야 했던 RGB 거리와 달리 삼각형을 이루는 정수들의 왼쪽 대각선, 오른쪽 대각선의 2가지 경우로만 이동 가능하므로 오히려 조건은 완화되었다.

딱 문제 보고나서 ‘어 이거 어제 풀었던거랑 비슷한데’ 라는 생각으로 시작했다.

결론부터 말하면 못풀어서 답보고 이해했는데, 접근방법이 아예 잘못되었다.

조건에서 주어졌듯이 2개의 이전 결과값을 비교하고 현재 삼각형 위치의 숫자를 더하면 되는거였는데, 일단 이 조건을 무시하고 최대값만 다 찾았다가 1차로 망했다.

잘못생각했다는걸 알아차리고 다른 방법을 생각해봤는데, 이것도 틀렸다.

뭔지 대충 설명하자면 최대값을 가질때의 배열 인덱스를 따로 받아두고 이 인덱스를 기준으로 다음 최대값을 찾는 방식.

DP에 대해 완벽히 이해하고 있는건 아닌것 같다.

예전 계산 결과 가져다 쓰는 문제구나 하는 느낌은 오는데, 예전 계산 결과를 어떤식으로 저장할 것이며 어떻게 가져다 쓸것인지에 대해 생각해내는 부분이 부족한 것 같다.

문제 보고도 뭔소린가 싶었던 옛날에 비해서는 많이 나아진 편이지만 아직도 갈길이 멀다…

---

정답 코드

//
// Created by Keith_Lee on 03/01/2019.
//

#include <iostream>
#include <cstring>

using namespace std;

int n;
int maximum = 0;

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

int main(){
    cin >> n;

    int DP[n+1][n+1];
    int tree[n+1][n+1];

    bzero(DP, sizeof(DP));
    bzero(tree, sizeof(tree));

    int inputNum;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++){
            cin >> inputNum;
            tree[i][j] = inputNum;
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++){
            DP[i][j] = max(DP[i-1][j-1], DP[i-1][j]) + tree[i][j];

            if(maximum < DP[i][j]){
                maximum = DP[i][j];
            }
        }
    }

    cout << maximum << '\n';

    return 0;
}

---