문제 설명

숫자 N에 대해서, N층부터 1층까지 존재하며
층을 내려갈때마다 숫자가 한개씩 증가하는 삼각형 구조를 이루고 있다.
이때, 꼭대기층부터 1층까지 숫자를 하나씩 선택하며 내려왔을때 합의 최댓값은?
단, i층에서 i-1층으로 내려갈때, 자신과 이웃한 두 개의 자식으로만 내려갈 수 있다.

접근

N층부터 1층까지 더할 수 있는 모든 경로에 대해 화살표를 한 번 해보자. 그러면, 중간중간에 겹치는 화살표를 가리키는 경우가 자주 발생한다.
즉, 중복을 줄이는게 문제의 핵심이다. 중복연산을 줄인다는 것은 보통 DP를 말한다.
그래서 다음과 같이 점화식을 생각해볼 수 있다.

N층의 i번째를 포함해서 N층까지 더했을때의 합 =
Math.max(그 윗층의 i-1번째까지 더했을때, 그 윗층의 i 번째까지 더했을때) + N층의 i번째 값

코드

import java.util.*;
import java.io.*;

public class Main {

    static int N;
    static ArrayList<Integer>[] tree;
    static ArrayList<Integer>[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        tree = new ArrayList[N + 1];
        dp = new ArrayList[N + 1];

        for (int i = 1; i < N + 1; i++) {
            tree[i] = new ArrayList<>();
            dp[i] = new ArrayList<>();
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < i; j++) {
                tree[i].add(Integer.parseInt(st.nextToken()));
                dp[i].add(-1);
            }
        }
        dp[1].set(0, tree[1].get(0));
        System.out.println(solution());
    }

    static int solution() {
        int max = 0;
        for (int i = 0; i < N; i++) {
            max = Math.max(max, dfs(N, i));
        }
        return max;
    }

    static int dfs(int curRow, int curCol) {
        if (dp[curRow].get(curCol) != -1) return dp[curRow].get(curCol);
        if (curCol == 0) {
            dp[curRow].set(curCol, tree[curRow].get(curCol) + dfs(curRow - 1, curCol));
        } else if (curCol + 1 == curRow) {
            dp[curRow].set(curCol, tree[curRow].get(curCol) + dfs(curRow - 1, curCol - 1));
        } else {
            dp[curRow].set(curCol, tree[curRow].get(curCol) + Math.max(dfs(curRow - 1, curCol - 1), dfs(curRow - 1, curCol)));
        }
        return dp[curRow].get(curCol);
    }
}

메모리 조금이라도 아끼려고 ArrayList로 했는데, 여기서 다른사람들 풀이보다 100ms정도 더 걸린듯 싶다.