백준 1932 - 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

이전에 풀었던 DP 문제처럼

optimal substructure를 어떻게 구성하느냐가 관건이다.

 

n(n+1)/2개의 정수를 2차원 배열 cost에 입력받고,

현재 위치까지의 합을 저장할 2차원 배열 sum을 생성한다.

 

이때 sum[i][j]의 값은 다음과 같다.

cost[i][j] (i = j = 0)

sum[i-1][0] + cost[i][0] (i > 0, j = 0)

sum[i-1][i-1] + cost[i][j] (i > 0, j = i)

max(sum[i-1][j-1], sum[i-1][j]) + cost[i][j] (i > 0, 0 < j < i)

 

sum[i-1][j-1]은 대각선 왼쪽 위, sum[i-1][j]는 대각선 오른쪽 위를 나타낸다.

j의 값이 0 또는 i일 때는 각각 왼쪽 위와 오른쪽 위가 존재하지 않으므로

최대값을 비교할 필요가 없다.

 

마지막으로 sum의 n-1번째 행에서 최대값을 찾아 반환한다.

 

배운 내용 : 배열의 인덱스 범위를 고려하며 풀기