[JAVA] 백준 1932 정수 삼각형

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

1932번: 정수 삼각형

- 크기가 5인 정수 삼각형 

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

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

 

 

풀이 과정 

 

 

[백준] 1932번 : 정수 삼각형 - JAVA [자바] (tistory.com)

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

[백준] 1932번 : 정수 삼각형 — BigKwangs 기술 블로그 (tistory.com)

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

 

- 정수삼각형을 타고 아래로 내려가면서 현재 칸까지 왔을 때 숫자를 더한 경우 가능한 최댓값을 기억

- 2번째 줄에서는 10와 15를 기억

- 3번째 줄에서는 16과 15를 기억

 

- n번째 줄에서는, 맨 처음과 끝 값은 바로 위의 값을 더한 값을, 그리고 중간에 있는 1번째값부터 n-1번째 값까지는 위의 두가지 값중에 큰 것만 더해서 기억시키면 됨 

 

 

- n-1행을 복사하고, Math.max(memo[i+1][j], memo[i+1][j+1])으로 memo[0][0]에 최댓값을 저장하는 방식 

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static Integer triangle[][];
    static Integer memo[][];
    static int n;
    
    static int df(int depth, int idx)
    {
        //마지막 행일 경우 현재 위치의 memo값 반환
        if(depth==n-1) 
            return memo[depth][idx];
        
        //탐색하지 않았던 값일 경우 다음 행의 양쪽 값 비교 
        if(memo[depth][idx]==null)
        {
            memo[depth][idx] = Math.max(df(depth+1,idx), df(depth+1, idx+1)) + triangle[depth][idx];
        }
        return memo[depth][idx];
    }
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        n = Integer.parseInt(br.readLine());
        triangle = new Integer[n][n];
        memo = new Integer[n][n]; //범위가 0부터 시작하므로, 빈공간을 체크하기 위해서 Integer 배열을 사용 
        
        for(int i=0; i<n; i++)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<=i; j++)
            {
                triangle[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
       for(int i=0; i<n; i++)
       {
           //가장 마지막 행의 값들을 memo의 마지막행에도 똑같이 복사
           memo[n-1][i] = triangle[n-1][i];
       }
       
        bw.write(df(0,0)+"");
        
        bw.flush();
        bw.close();
        
    }
    
}