[JAVA] 백준 1932번 : 정수 삼각형

1932번: 정수 삼각형

문제

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

- 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램

- 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택가능

- 삼각형의 크기는 1 이상 500 이하이다.

- 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

 

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다

 

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력

 

 

풀이

일단 정수삼각형을 다 넣고, 그 합을 비교하기 위해선 이중배열을 사용해야한다고 생각했다.

 

정수삼각형의 정수를 넣는 이중배열 list, 그 경로에 있는 정수의 합을 넣는 이중배열 dp이라고하자.

 

예를들어 세번째 줄의 dp 값을 구하게 된다면,

dp[3][1] = dp[2][1] + list[3][1]

dp[3][2] = MAX(dp[2][1] + list[3][2], dp[3][2]+list[3][2])

dp[3][3] = dp[2][2]+list[3][3] 

식임을 알 수 있다.

 

이때 각 줄의 맨 왼쪽과 오른쪽에 위치한 정수들은 그대로 경로를 따라 쭉 더해주기만 하면 되지만,

중간에 위치한 정수들은 현재 층의 위에 존재하는 대각선 왼쪽 또는 대각선 오른쪽의 경로를 중 합이 최대가 되는 경로의 값만 저장해주어야한다. 

 

따라서 정수가 맨 왼쪽에 위치할때, 중간에 위치할때, 맨 오른쪽에 위치할 때의 경우를 나눠서 계산해준다.

 

하지만 우리가 마지막에 출력해야하는 값은 합이 최대가 되는 경로에 있는 수의 합이므로 max를 따로 만들어줘서 매번 갱신해주어야한다.

 

list와 dp는 이런식이다.

list[1][1] = 7 dp[1][1] = 7	X	X	X
list[2][1] = 3 dp[2][1] = 7+3 =dp[1][1]+list[2][1]	list[2][2] = 8 dp[2][2] = 7+8 =dp[1][1]+list[2][2]	X	X
list[3][1] = 8 dp[3][1] = 7+3+8 = dp[2][1]+list[3][1]	ist[3][2] = 1 dp[3][2] = MAX(7+3+1, 7+8+1) = MAX(dp[2][1], dp[2][2])+list[3][2]	list[3][3] = 0 dp[3][3] = 7+8+0 = d[2][2]+list[3][3]	X

 

코드를 적을 때 주의할 점은 이중 for문을 돌릴 때 입력받아야하는 모양이 정수삼각형으로 n번째 줄에는 n개의 정수가 들어간다는 점이다. 따라서 j의 범위는 i와 같아질 때 까지!

public class bj1932 {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		
		int n = s.nextInt(); // 삼각형의 크기 n 입력받음
		
		// 정수삼각형 입력받음
		int list[][] = new int[501][501];
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=i;j++) {
				list[i][j]=s.nextInt();
			}	
		}
		
		// 경로의 합과 최대값 구함
		int [][] dp = new int[501][501];
		int max=0;
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=i;j++) {
				if(j==1) dp[i][1]=dp[i-1][1]+list[i][1]; // 맨 왼쪽 줄
				dp[i][j]=Math.max(dp[i-1][j-1],	dp[i-1][j])+list[i][j];
				if(j==i)dp[i][i]=dp[i-1][i-1]+list[i][i]; // 맨 오른쪽 줄
				max = Math.max(max, dp[i][j]);
			}			
		}
		
		System.out.println(max);
		s.close();
	}
}