다이나믹프로그래밍1- 백준 1932번 정수 삼각형

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

IDEA

배열을 triangle 이라고 하자. 

그렇다면 cost배열에 triangle[i][j]에 도달하는데 걸리는 최대 비용을 저장해주자.

그림보다는 입력형태를 봐야 규칙이 보인다. 그림에선 대각선이지만 입력배열에서는 대각선이 아니기때문이다.

맨 처음 0번째일때는 따로 드는 비용이 없기 때문에 cost = triangle 이다. 

 

1. 열이 0일때
   그림에서는 열이 0일 떄는 자신의 오른쪽 위에서 밖에 오지 못한다.
   입력배열기준으로 생각해보면 열이 0일떄는 자신의 바로 위에서만 올 수 있다. 
   즉 triangle[i][0]에 도착할 수 있는 최대 비용 = trianlge[i-1][0]까지의 비용 + triangle[i][0] 이다. 
   
   
2. 열이 i일때
   가장 오른쪽에 위치할떄를 얘기하는 것이다. 
   입력배열 기준으로 열이 i일때는 자신의 바로 왼쪽 위에서만 올 수 있다. 
   즉, triangle[i][i]에 도착할 수 있는 최대 비용 = trianlge[i -1][i -1]까지의 비용 + triangle[i][i] 이다.
   
   
3. 이외 열이 1 ~ i-1 사이 일때
   이 때는 그림을 기준으로 자신의 왼쪽 위, 오른쪽 위에서 올 수 있다.
   입력배열 기준으로는 자신의 바로 위쪽 , 왼쪽 위에서 올 수 있다.
   triangle[i][j]에 도착할 수 있는 최대 비용
   = max ( trianlge[i-1][j]까지의 비용, triangle[i-1][j-1]까지의 비용)  + triangle[i][j] 이다. 

triangle 배열 

7
3	8
8	1	0
2	7	4	4
4	5	2	6	5

cost 배열

7
10	15
18	16	15
20	25	20	19
24	30	27	26	24

 

CODE

#include <iostream>
#include<algorithm>
using namespace std;

int triangle[500][500] = {0};
int cost[500][500] = {0};
int n;

void  dp(int idx) {
	//idx = 0인 경우 cost 값 = triangle 값
	if (idx == 0) cost[0][0] = triangle[0][0];
	//idx !=0 인 경우
	else {
		//j=0일 떄 [i-1][j] 값 + triangle 값 
		cost[idx][0] = cost[idx - 1][0] + triangle[idx][0];
		//그 외의 경우 [i-1][j-1] , [i-1][j] 중 최솟값 + triangle 값
		for (int j = 1; j < idx; j++) {
			cost[idx][j] = max(cost[idx - 1][j - 1], cost[idx - 1][j]) + triangle[idx][j];
		}
		//j = i일 떄, [i-1][j-1] + triangle 값 
		cost[idx][idx] = cost[idx - 1][idx - 1] + triangle[idx][idx];
	}
}


int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			scanf("%d", &triangle[i][j]);
		}
	}
	for (int i = 0; i < n; i++) dp(i);
	printf("%d" , *max_element(cost[n - 1], cost[n - 1] + n));
}