[백준]1932 정수삼각형

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        int[][] triangle = new int[n][n];
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int j = 0;
            while (st.hasMoreTokens()) {
                triangle[i][j] = Integer.valueOf(st.nextToken());
                j++;
            }
        }

        int max = 0;

        // 초기값 세팅
        dp[0][0] = triangle[0][0];
        for(int j=1; j<triangle.length; j++) {
            for (int k = 0; k < triangle[j].length; k++) {
                int now = triangle[j][k];
                if(k==0)
                    dp[j][k] = now+dp[j-1][k];
                else
                    dp[j][k] = Math.max(now+dp[j-1][k-1], now+dp[j-1][k]);
                //System.out.println(dp[j][k]);
            }
        }
        for (int m = 0; m < triangle.length; m++) {
            max = Math.max(max, dp[n-1][m]);
        }
        System.out.println(max);
    }
}

👩‍💻 풀이
완전 dp의 정석인 문제가 아닐까 싶다!
일단 0,0 에 초기값을 세팅해주고 삼각형만큼 반복문을 돌린다.
컴퓨터는 대각선으로 이동할 수 없으니 직각삼각형으로 만들어 2차원 배열에 담아 현재 위치 기준 왼쪽위와 바로위의 값을 현재값과 더해 차례로 비교한다.
모든 삼각형의 첫번째는 바로 위의 값밖엔 더할 게 없으므로 분기해주고 나머지는 Math.max 함수를 통해 최대값을 넣는다.
삼각형의 맨 마지막줄에 가장 큰 합이 들어있으므로 반복문을 돌려 가장 큰값을 출력해주면 끝!
역시 설명이 제일 어렵다.. max 값을 찾는 과정을 따로 빼주지 않고 dp 배열을 저장하는 포문 안에서 찾으려니 틀렸다고 떴다. 왜그런지는 지금부터 다시 봐봐야겠다 ㅠ