[백준/BOJ] 1932번 정수 삼각형 (C++)

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

DFS + DP 유형의 문제입니다.

입력값을 2차원 배열에 넣어주고, DFS를 통해 (0, 0) 에서 시작하여 n-1번째 행의 모든 열을 방문합니다. 리프 노드에서 다시 루트 노드로 올라가면서, 누적 최대값을 갱신하게 됩니다.

 

#include <iostream>
#include <cstring>
using namespace std;

int n;
int map[501][501];
int dp[501][501];

int DFS(int x, int y) {
    if(dp[x][y] != -1) return dp[x][y]; // 이미 방문한 경우 저장된 값 리턴
    if(x == n - 1) return map[x][y]; // 맨 끝 노드에 도착
    return dp[x][y] = max(DFS(x + 1, y), DFS(x + 1, y + 1)) + map[x][y]; // 아래 방향, 오른쪽 아래 대각선 중 최대 값 + 현재 값
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            cin >> map[i][j];
        }
    }
    
    memset(dp, -1, sizeof(dp));
    cout << DFS(0, 0);
}