[백준] 1932번 정수 삼각형 JAVA (자바) 풀이

문제 1932번 (DP)

 

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

 

 :  위 그림은 크기가 5인 정수 삼각형

    맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 내려온다

    선택된 수의 합이 최대가 되는 경로를 구해라

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

    삼각형의 크기는 1 이상 500 이하 / 삼각형을 이루고 있는 각 수 범위는 0 이상 9999 이하

 

 

[입력]

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

 

 

[출력]

 

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

 

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)	보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결	작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization)	타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때	모두 계산해야 답이 나올 때
재귀	반복문
시간 복잡도 O(n)	시간 복잡도 O(n)

 

1. dp 규칙 찾기

• 열 맞춰서 숫자를 세워보자
  • 7 
    3 8
    8 1 0
  • 위와 같은 경우 현재 숫자를 1이라고 할 경우 같은 열과 바로 이전 열의 숫자 중 max값을 택해야한다
  • dp[i-1][j-1], dp[i-1][j]

 

• 최종 dp는 모든 열 중에 최대값!
  • 최종 출력할 값은 N으로 행이 정해져 있다
  • 열마다 dp값이 있기 때문에 그 중 max값을 출력한다

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int arr[][] = new int[N][3];
        
        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0]=Integer.parseInt(st.nextToken());
            arr[i][1]=Integer.parseInt(st.nextToken());
            arr[i][2]=Integer.parseInt(st.nextToken());
        }
        
        int dp[][] = new int[N][3];
        dp[0][0] = arr[0][0];
        dp[0][1] = arr[0][1];
        dp[0][2] = arr[0][2];
        
        for(int i=1;i<N;i++){
            dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+arr[i][0];
            dp[i][1]=Math.min(dp[i-1][0],dp[i-1][2])+arr[i][1];
            dp[i][2]=Math.min(dp[i-1][0],dp[i-1][1])+arr[i][2];
        }
        
        System.out.println(Math.min(dp[N-1][0],Math.min(dp[N-1][1],dp[N-1][2])));
    }
}

 

 

 [해설]
     

 :  BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int arr[][] = new int[N+1][N+1];  arr 배열
    int dp[][] = new int[N+1][N+1];  dp 배열
        
 :  for(int i=1;i<=N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1;j<=i;j++){
                arr[i][j]=Integer.parseInt(st.nextToken());  arr 입력받기
            }
    }
        
 :  for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){ 이전 행의 이전 열과 현재 열 값 중 최대값 출력 후
                dp[i][j]=Math.max(dp[i-1][j-1], dp[i-1][j])+arr[i][j];  현재 값 더하기
            }
    }
        
 :  int result =0;
    for(int i=1;i<=N;i++){  N개의 열 중에 최대값 구하기
            result = Math.max(dp[N][i],result);
    }
    

 :  System.out.println(result);  결과 출력
    

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

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

 

 

 

 

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *