Baekjoon1932: 정수 삼각형

정수 삼각형

한국어   

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

52465

28961

21675

58.689%

문제

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

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

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

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

출력

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

 

풀이

Bottom → Top

삼각형에서 높이를 항으로 생각한다. 맨 윗줄은 1항 2번째 줄은 2항, 3번째 줄은 3항... n번째 줄은 n항이다

dp는 매 줄에서의 최대값을 기록한다. 각 항에서의 최대값을 기록할 수 있다.

→ 맨 위 꼭대기 7의 최대값은 7이며 dp[1][1]=7이라고 할 수 있다 

→ 두번째 줄 3에서의 최대값은 이전항 7에서부터 왔으므로 dp[2][1] =10 이다

→ 두번째 줄 8에서의 최대값은 이전항 7에서부터 왔으므로 dp[2][2] =15 이다

→ 세번째 줄 1에서의 최대값은 dp[2][1]=10과 dp[2][2]=15중 더 큰 값을 가져온다. dp[3][2]=는 18+1 =19가 된다

 

     ※ 세번째 줄을 통해 dp[n][j]를 표현할 수 있다. dp[n][j] = Math.max( dp[n-1][j-1] , dp[n-1][j] )

     ※ 하지만 맨 끝에 있는 숫자들은 선택권이 없다. 아래 삼각형에서 2와 4는 이전 줄 맨 끝에서 이동한 결과이다.

현재줄에서 dp[n][j]는 다음의 규칙으로 기록된다

1) dp[n][j]가 줄에서 맨 처음에 있는 값일 때: dp[n][처음항] = dp[n-1][처음항] + 현재 숫자   

2) dp[n][j]가 줄에서 맨 마지막에 있는 값일 때: dp[n][마지막항] = dp[n-1][마지막항] + 현재 숫자 

3) 그 외 모든 dp[n][j]: Math.max( dp[n-1][j-1] , dp[n-1][j] ) + 현재 숫자

import java.io.*;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n =Integer.parseInt(st.nextToken());
		int[][] triangle = new int[500][500]; //[500][500] 배열 생성
		Integer[][] dp = new Integer[n][500]; //제한조건에서 n의 최대는 500이다
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<i+1;j++) {
				triangle[i][j]=Integer.parseInt(st.nextToken());
			}
		} //triangle 배열에 입력값들을 모두 넣어준다
        
		dp[0][0]=triangle[0][0]; //dp[0][0]은 삼각형 맨 꼭대기므로 값이 정해져있다
        
		int max=dp[0][0]; //주의)1줄일 때 반복문이 실행 안되므로 max의 처음값은 0이 아닌 dp[0][0]
        
		for(int i=0; i<n; i++) {
			for(int j=0; j<=i; j++) {
				if(dp[i][j]==null) {
                
					if(j==0) { //줄에서 맨 처음
						dp[i][j]=dp[i-1][j]+triangle[i][j];
                       
					}else if(j==i) { //줄에서 맨 끝
						dp[i][j]=dp[i-1][j-1]+triangle[i][j];
                        
					}else { //그 외
						dp[i][j]=Math.max(dp[i-1][j-1]+triangle[i][j],dp[i-1][j]+triangle[i][j]);
					}
					max=Math.max(max, dp[i][j]);
				}
			}
		}
		System.out.print(max);
	}
}