[BOJ1932] 정수 삼각형

맨 위에서 아래까지 더하며 내려오는 최대 값의 경로

• 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 오른쪽에 있는 것 중에서만 선택
• 삼각형 크기는 1이상 500이하, 모두 정수, 범위 0 ~ 9999

입력

• 첫째 줄에 삼각형 크기 n ( 1 <= n <= 500)
• 둘째줄부터 n개의 줄에 정수 삼각형

출력

• 합이 최대가 되는 경로에 있는 수의 합

설계

• 경로를 따져보았을 때, 맨 왼쪽과 맨오른쪽은 단순히 위의 값을 현재 값에 더해주면 된다.
• 하지만 다른 인덱스에서는 왼쪽 위, 오른쪽 위 대각선에서 오는 두 가지의 경로가 있기 때문에, 이것의 max 값을 따져봐야한다.

피드백

• 배열 인덱스를 정확하게 나누는 것이 관건인데, c++의 포인터 특성 탓에 이상하게 인덱싱을 해도 정답이 나왔다.
• 음수, 또는 최대 인덱스 이상의 인덱스를 참조해도 컴파일 오류가 나지 않았다.
• 따라서, 아래의 핵심 코드 한 줄로 풀이가 가능했다.
  dp[i][j] = MAX(dp[i-1][j-1] + dp[i][j], dp[i-1][j] + dp[i][j]);
• 하지만 코드를 보고 이해하기 위해서는 정확하게 구분하여 나누는 것 필요

How I solved(click to github)

---

ref :
BOJ1932