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

🔺 문제

1932번: 정수 삼각형

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    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[][] A = new int[n + 1][n + 1];
        
        // 입력 받기
        for(int i = 1 ; i <= n ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j = 1 ; j <= i ; j++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        if(n == 1) {
            System.out.println(A[1][1]);
            return;
        }
        
        // dp 배열 채우기
        int[][] dp = new int[501][501];
        dp[1][1] = A[1][1];
        
        // 첫 번째 열 따로 채우기
        for(int i = 2 ; i <= n ; i++) {
            dp[i][1] = dp[i-1][1] + A[i][1];    
        }
        
        int max = 0;
        for(int i = 2 ; i <= n ; i++) {
            for(int j = 1 ; j <= i ; j++) {
                if(i - 1 < 1 || j - 1 < 1) continue;    // 범위 벗어나는 경우
                
                dp[i][j] = Math.max(dp[i][j], Math.max(dp[i-1][j], dp[i-1][j-1]) + A[i][j]);
                max = Math.max(max, dp[i][j]);
            }
        }
        
        for(int i = 1 ; i <= n ; i++) {
            for(int j = 1 ; j <= i ; j++) {
                System.out.print(dp[i][j] +" ");
            }
            System.out.println();
        }
        
        System.out.println(max);
    }
}

✅ 해결 아이디어
✔ DP (Bottom-Up)

 

1) 테이블 정의하기

dp[i][j] : 위치(i, j)에서 합이 최대가 되는 값

 

 

2) 점화식 찾기

dp[i][j] = Math.max(dp[i][j], Math.max(dp[i-1][j], dp[i-1][j-1]) + A[i][j]);

 

dp 배열의 왼쪽 대각선 위 값과 dp 배열의 바로 위 값 중 큰 값을 구하고,

이 값과  A 배열의 현재 위치 값을 더해

dp 배열의 현재 위치에 채워넣는다.

 

(풀고 보니,,, 기존 dp[i][j] 값과 비교는 하지 않아도 된다.)

 

 

3) 초기값 설정하기

dp[1][1] = A[1][1];

 

 

 

💥 유의사항

- n이 1인 경우           ⇨ 입력받은 값 바로 출력
- n이 2 이상인 경우 ⇨ dp 배열 채우고 출력

 

 

---

🔺 다른 풀이들

- 값 입력받으면서 바로 dp 배열 채우고 max 값 계산하는 멋진 콛,,,

로그인

 

- Top-Down 방식 코드

로그인

 

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

---

💬 느낀 점

점화식 떠먹여주는 문제라 혼자 풀긴 했다만,,,

시간이 오래 걸려서 좀 아숩다...

담에 풀이 시간 줄이면 되지!

 

1회독	2회독	3회독	4회독	5회독
V