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

가영·2021년 1월 22일
0

알고리즘

목록 보기
5/41
post-thumbnail

입력예시에서 힌트를 얻어 문제를 풀었다. 😉
나는 삼각형을 이루는 정수를 tri[][]에 저장했는데, tri[i][j] 에서 접근할 수 있는 수는 tri[i+1][j]tri[i+1][j+1]이었다. 그래서 그 둘 중에 큰 값과 자기 자신을 더해서 dp[i][j]에 저장해두면 된다.

나는 밑에 줄부터 시작했다. 그래서 마지막 줄의 dp는 (dp[N-1]) 미리 값을 채워주었다. 👉🏻 dp[N-1] = tri[N-1]

import java.util.Scanner;

public class boj1932 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] tri = new int[N][N];
        int[][] dp = new int[N][N];
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < i+1; j++) {
                tri[i][j] = sc.nextInt();
            }
        }
        dp[N-1] = tri[N-1];
        for(int i = N-2; i >= 0; i--) {
            for(int j = 0; j <= i; j++) {
                dp[i][j] = tri[i][j] + Math.max(dp[i+1][j], dp[i+1][j+1]);
            }
        }
        System.out.println(dp[0][0]);
    }
}

다른 사람들 풀이를 보면 위에서부터 하는 경우도 많았다. 그럴 땐 max 변수를 따로 두고 최댓값을 저장하면서 하면 된다.

0개의 댓글