문제

풀이 과정

요약

누적합을 이용한 문제.

상세

1. 임의의 좌표 $R$, $C$ 가 존재하는 경우, $R-1$ 계층에서, 해당 임의의 좌표에 도달할 수 있는 경우의 수는 2가지이다.

   • $R-1$, $C-1$ 좌표이거나

   • $R$, $C-1$ 좌표이다.

2. 델타를 이용하여 1 계층을 시작으로 바로 직전 위 층에서 도달할 수 있는 경우의 수를 보며 값을 누적해간다. 단 인덱스 에러가 나는 좌표도 있으니 처리해주자.

3. 그렇게 누적한 값들 가운데 최댓값이 정답이 된다.

정답

#include <string>
#include <vector>
using namespace std;
int dr[2] = {-1, -1}, dc[2] = {0, -1};
int solution(vector<vector<int>> triangle) {
    int answer = 0;
    for (int i = 1; i < triangle.size(); i++) {
        for (int j = 0; j <= i; j++) {
            int tmp = triangle[i][j];
            for (int d = 0; d < 2; d++) {
                int nr = i + dr[d];
                int nc = j + dc[d];
                if (nr < 0 || nc < 0 || nc >= i) continue;
                triangle[i][j] = max(tmp + triangle[nr][nc], triangle[i][j]);
                answer = max(triangle[i][j], answer);
            }
        }
    }
    return answer;
}