문제
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다.
맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.
삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.
입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.
출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.
예제 입력 1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5예제 출력 1
30문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ1932 {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N=Integer.parseInt(br.readLine());
int[][] tri=new int[N][N];
int[][] dp=new int[N][N];
for(int i=0;i<N;i++){
st=new StringTokenizer(br.readLine());
for(int j=0;j<i+1;j++){
tri[i][j]=Integer.parseInt(st.nextToken());
}
}
dp[0][0]=tri[0][0];
for(int i=0;i<N-1;i++){
for(int j=0;j<i+1;j++){
//왼쪽 대각선 (본인과 열 값, j가 같음)
dp[i+1][j]=Math.max(dp[i+1][j],dp[i][j]+tri[i+1][j]);
//오른쪽 대각선
dp[i+1][j+1]= Math.max(dp[i+1][j+1],dp[i][j]+tri[i+1][j+1]);
}
}
int max=0;
for(int i=0;i<N;i++){
if(max<dp[N-1][i]) max=dp[N-1][i];
}
System.out.print(max);
}
}DP를 이용하면 쉽게 풀 수 있는 문제였다.
문제를 보면 한 줄씩 넘어갈때마다 숫자의 개수 또한 1개씩 늘어나는 것을 확인할 수 있는데 제일 위에서부터 왼쪽 아래, 오른쪽 아래로 차근차근 따라오면서 값을 더해주면 가장 큰 합을 구할 수 있다.
N x N 크기의 배열을 만들어 왼쪽 아래, 오른쪽 아래를 비교하면 인덱스는 각각 [i+1][j], [i+1][j+1]을 비교하게 된다.
이 점을 생각하고 DP를 사용하여 문제를 풀어보면 된다.
각 지점에서의 합 구하기
dp[0][0]=tri[0][0];
for(int i=0;i<N-1;i++){
for(int j=0;j<i+1;j++){
//왼쪽 대각선 (본인과 열 값, j가 같음)
dp[i+1][j]=Math.max(dp[i+1][j],dp[i][j]+tri[i+1][j]);
//오른쪽 대각선
dp[i+1][j+1]= Math.max(dp[i+1][j+1],dp[i][j]+tri[i+1][j+1]);
}
}경로를 지나오면서 최대 합을 구해야하기 때문에 해당 지점에서 왼쪽 아래, 오른쪽 아래로 값을 더해주어 최대값을 갱신한다.
숫자 합의 정보를 담기 위해 dp라는 배열을 만들어 각 지점에서 왼쪽 아래를 바라봤을때 최대 값, 오른쪽 아래를 바라봤을 때 최대값을 배열에 넣어준다.
5 7
3 8 3위와 같은 경우를 생각해보면 경로 값은
5 7
8 13 10가 된다.
5의 위치에서 3을 바라봤을때 7+3의 값을, 8을 바라봤을 때 5+8의 값을 넣어주게 되는데 이때, 7이 바라보는 경우를 생각하여 최대값을 넣는 경우도 고려해야한다.
즉, 처음에는 5가 바라보는 경우만을 생각했을 때 dp 배열에는 다음과 같은 값이 저장되어있다.
5 7
8 13 07이 왼쪽 아래와 오른쪽 아래를 바라보는 경우를 생각해보면 왼쪽아래에 이미 값이 적힌 13과 7+8의 값을 비교하여 큰 값을 저장해야한다.
이때, 7+8=15 의 값이 13보다 크기 때문에 13의 위치에는 15의 값으로 갱신해주고 오른쪽 아래에는 7+3=10 의 값을 넣어주어 dp 배열을 완성한다.
경로의 최대합 구하기
int max=0;
for(int i=0;i<N;i++){
if(max<dp[N-1][i]) max=dp[N-1][i];
}
System.out.print(max);위 과정을 반복하여 dp 배열을 모두 채워주면 마지막 행에는 각 경로의 합을 구할 수 있다.
그 중 가장 큰 값을 찾으면 답을 출력할 수 있다.
