백준
백준 1932 - 정수 삼각형
황태건
2023. 5. 8. 14:52
https://www.acmicpc.net/problem/1932
1932번: 정수 삼각형
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
www.acmicpc.net
이전에 풀었던 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번째 행에서 최대값을 찾아 반환한다.
배운 내용 : 배열의 인덱스 범위를 고려하며 풀기