백준 1932 정수 삼각형

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

1932번: 정수 삼각형

동적계획법 문제였습니다.

 

[문제설명]

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

 

점화식을 세우기 위해 규칙을 찾아보았습니다.

1. 2차원 배열의 열 번호가 1인 경우(triangle[i][1]) 는 바로 위의 열번호가 1인 배열의 합산값(sum[i][1])을 자기 자신과 더해주면된다.

if(j==1){
	sum[i][j] = sum[i-1][j] + triangle[i][j];
}

2. 열 번호가 행 번호와 같은 경우(triangle[i][j], i==j) 바로위의 열과 행의 번호가 같은 배열의 합산값(sum[i][j], i==j)을 자기 자신과 더해주면된다.

 else if(j==i){
	sum[i][j] = sum[i-1][j-1] + triangle[i][j];
}

3. 그 외에 값들은 바로위의 두개의 합산값(sum[i-1][j-1] , sum[i-1][j]) 중 큰 값을 선택해 주면 된다. 

 else{
	sum[i][j] = Math.max(sum[i-1][j-1],sum[i-1][j]) + triangle[i][j];
}