[DAY76] Algorithm : Integer Triangle

전형적인 최적화 문제로, "최적 부분 구조"를 이용하여 동적 계획법(DP)으로 상향식(Bottom-up)으로 해결했다.

---

❓ 문제 분석

• 목표: 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중 거쳐간 숫자의 합이 가장 큰 최댓값을 구하는 것이 목표이다.

• 제약 조건: 삼각형의 높이 $N$은 1 이상 500 이하이다. ($N \le 500 \rightarrow$ $O(N^2)$ 복잡도 허용. 총 계산 횟수는 약 $500^2 / 2 = 125,000$ 정도로 시간 제한에 여유가 있었다.)

• 핵심 키워드: "경로", "합이 가장 큰", "대각선 이동" (최적화 문제에서 자주 나오는 키워드로, DP 접근의 힌트가 되었다.)

---

💡 풀이 설계

1. 시도했던 접근 (First Attempt)

• 처음에는 **DFS(깊이 우선 탐색)**를 사용하여 꼭대기부터 바닥까지 모든 경로를 탐색하고, 그중 최댓값을 구하려고 했다.
• 하지만 삼각형의 높이 $N$에 대해 경로의 수는 $2^{N-1}$개에 달한다. $N=500$인 경우 시간 초과가 명백하게 발생할 것이라 판단하여 이 방법은 기각했다.

2. 최종 해결책 (Solution)

• 이 문제는 **"최적 부분 구조(Optimal Substructure)"**를 가지고 있다. 특정 칸 $(i, j)$에 도달하는 최대 합 경로는 그 바로 윗 행 $(i-1)$에 있는 칸들의 최대 합 경로에 의해 결정된다.
• 따라서, **동적 계획법(DP)**을 사용하여 문제를 해결하는 것이 최적의 방법이다.
• 공간 복잡도를 아끼기 위해 입력 배열 triangle을 그대로 DP 테이블로 활용하여 값을 갱신하는 In-place DP 방식을 채택했다.
• 예상 시간 복잡도: $O(N^2)$ (N은 삼각형의 높이)
• 알고리즘 흐름:

    1. 삼각형의 두 번째 행($i=1$)부터 시작하여 마지막 행까지 순회하는 **바깥 반복문(행)**을 설정한다.
2. 각 행 내의 모든 칸에 대해 **안쪽 반복문(열)**을 돌며 DP 값을 갱신한다.
3. 점화식을 적용하여 triangle[i][j]에 (꼭대기 $\to$ 현재 칸)의 최대 합을 덮어쓴다. (가장자리 칸 예외 처리 포함)
4. 모든 계산이 끝난 후, 가장 아랫줄의 값들 중에서 최댓값을 최종 결과로 반환한다.

---

💻 코드 구현

#include <string>
#include <vector>
#include <algorithm>

using namespace std;


int solution(vector<vector<int>> triangle) {
    // DP를 위해 입력 배열 자체를 갱신한다 (In-place DP).
    
    int height = triangle.size();
    
    // 행 순회: 두 번째 행 (i=1)부터 시작한다. 첫 행은 이미 초기값이다.
    for (int i = 1; i < height; i++) {
        // 열 순회: 해당 행의 모든 요소 (j=0부터 j=i까지)를 순회한다.
        for (int j = 0; j <= i; j++) {
            
            // 점화식 적용 및 갱신
            if (j == 0) {
                // 가장 왼쪽 칸 (j=0): 위-왼쪽 경로가 없으므로, 바로 위에서 온다.
                triangle[i][j] += triangle[i - 1][j];
            }
            else if (j == i) {
                // 가장 오른쪽 칸 (j=i): 바로 위 경로가 없으므로, 위-왼쪽에서 온다.
                triangle[i][j] += triangle[i - 1][j - 1];
            }
            else {
                // 일반 칸: 위-왼쪽 (j-1)과 바로 위 (j) 경로 중 최댓값을 선택한다.
                triangle[i][j] += max(triangle[i - 1][j - 1], triangle[i - 1][j]);
            }
        }
    }
    
    // 마지막 행에 저장된 DP 값들 중 최댓값을 찾는다.
    int answer = *max_element(triangle[height - 1].begin(), triangle[height - 1].end());

    return answer;
}

---

🐛 시행착오 및 디버깅

• 문제점: DP 점화식 적용 시 가장자리 조건을 빼먹을 뻔했다.
• 원인: 일반적인 칸의 $\max$ 로직만 생각하고, $j=0$일 때 $j-1$ 인덱스(음수) 접근 오류가 발생할 수 있다는 점을 간과했다.
• 해결: if-else if-else 구문을 사용하여 $j=0$ (가장 왼쪽), $j=i$ (가장 오른쪽), 그리고 그 외 일반적인 칸으로 명확하게 나누어 예외 없이 처리하도록 코드를 구성했다.

---

✅ 오늘의 회고

항목	내용
유형	동적 계획법 (Dynamic Programming, DP)
체감 난이도	하
복잡도	(시간: $O(N^2)$, 공간: $O(1)$ 추가 공간)
새로 배운 것	In-place DP를 통한 공간 복잡도 최적화 기법을 적용해 보았다. 입력 배열을 DP 테이블로 재활용하면 추가 메모리 사용 없이 문제를 해결할 수 있다는 것을 다시 한번 확인했다. 또한, std::max_element 사용법을 익혔다.