종식당

[백준 1932] 정수 삼각형 본문

백준

[백준 1932] 정수 삼각형

종식당 2024. 12. 18. 10:47
728x90
반응형

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


  • 문제설명
    삼각형 모양으로 정수들이 주어지는데 맨 위층부터 아래로 내려오면서 숫자를 층마다 하나씩 선택하게 된다. 선택한 값들의 합이 최대가 되는 숫자를 출력하면 된다. 이때 선택할 수 있는 값을 바로 위 층에서 왼쪽 대각선 오른쪽 대각선에서만 선택할 수 있다.
  • 제출코드     
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 [][] lst = new int[n+1][n+1];
        int [][] dp = new int[n+1][n+1];

        for(int i = 1;  i <= n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 1; j <=i; j++){
                lst[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 1;  i <= n; i++){
            for(int j = 1; j <=i; j++){
                dp[i][j] = lst[i][j] + Math.max(dp[i-1][j-1],dp[i-1][j]);
            }
        }

        int max = -1;

        for(int i = 1; i<=n; i++){
            if(dp[n][i] > max){
                max = dp[n][i];
            }
        }
        System.out.println(max);

    }
}

 

코드설명
먼저 lst 2차원 배열을 만들어서 입력으로 받은 숫자들을 배열에 담아준다.
그러면 다음과 같이 배열에 담길 것이다.


그리고 dp배열을 하나 만들어 준다. 위에서부터 아래로 내려오면서 사진처럼 배열에 담았을 때 생각해 보면 바로 위의 값과 왼쪽 대각선의 값들 중에서 더할 값을 선택할 수 있다. 더했을 때 가장 큰 값이 되어야 하므로 max함수를 사용해서 두 값들 중에 큰 값을 선택해 해당 인덱스와 더해주면 된다. 그럼 이 dp배열에서 해당 인덱스는 거기까지의 최댓값이 저장되어 있는 셈이다.

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

 

위 코드를 가지고 for문을 돌면서 해당 인덱스까지 오면서의 최댓값을 각각의 index에 저장해 둔다.

 

그럼 마지막 행에서 최댓값을 출력해 주면 그 값이 정답이다.

 


728x90
반응형

'백준' 카테고리의 다른 글

[백준 14719 with JAVA] 빗물  (3) 2025.01.29
[백준 7562] 나이트의 이동  (1) 2025.01.06
[백준 9095] 1, 2, 3 더하기  (2) 2024.12.16
[백준 9935] 문자열 폭발  (0) 2024.11.01
[백준 3050] 나머지  (0) 2024.09.28